Complete Algebraic Reconstruction of Piecewise-Smooth Functions from Fourier Data

Dmitry Batenkov

Abstract

In this paper we provide a reconstruction algorithm for piecewise-smooth functions with a-priori known smoothness and number of discontinuities, from their Fourier coefficients, possessing the maximal possible asymptotic rate of convergence—including the positions of the discontinuities and the pointwise values of the function. This algorithm is a modification of our earlier method, which is in turn based on the algebraic method of K. Eckhoff proposed in the 1990s. The key ingredient of the new algorithm is to use a different set of Eckhoff's equations for reconstructing the location of each discontinuity. Instead of consecutive Fourier samples, we propose to use a "decimated" set which is evenly spread throughout the spectrum.

Introduction

In classical harmonic analysis, Fourier series provide an elegant representation of smooth, periodic functions, characterized by rapid convergence. However, real-world signals frequently contain "shocks" or discontinuities—such as step functions or square waves—that violate these smoothness assumptions. In these cases, Fourier series converge slowly and produce the "Gibbs phenomenon," characterized by persistent oscillations near the points of discontinuity.

To mitigate these effects, researchers employ "acceleration" techniques. These methods aim to identify the locations and magnitudes of jumps to subtract them from the signal, leaving a smooth remainder that can be reconstructed with high precision. The fundamental challenge lies in the accuracy of locating these discontinuities using a finite number of Fourier coefficients ($M$).

The Theoretical Limit of Reconstruction

For a function with $d$ continuous derivatives, theoretical analysis suggests that the maximum achievable accuracy for locating a jump is $O(M^{-d-2})$. While various algebraic methods, most notably those proposed by K. Eckhoff in the 1990s, attempted to reach this limit, previous implementations were often numerically unstable or only achieved "half" of the potential accuracy ($O(M^{-(d+2)/2})$). This paper introduces a modification to the algebraic approach that finally achieves the maximal asymptotic rate of convergence, resolving a long-standing conjecture in the field.

The Decimated Eckhoff Algorithm

The proposed "Decimated Eckhoff Algorithm" treats the identification of jump locations as an algebraic problem, specifically solving for the roots of a Prony-type polynomial. The core innovation lies in how the Fourier spectrum is sampled.

Traditional approaches typically utilize consecutive high-frequency Fourier coefficients (e.g., $k = M, M-1, M-2, \dots$). The author demonstrates that this consecutive sampling is sub-optimal. Instead, the new algorithm employs a "decimation" strategy:

  1. Localization: Using "bump functions," the algorithm isolates each discontinuity into a specific neighborhood, simplifying the global problem into several local ones.
  2. Decimation: Rather than consecutive samples, the algorithm selects Fourier coefficients that are evenly spread throughout the available spectrum (e.g., $k = N, 2N, 3N, \dots$ where $N \approx M/d$).
  3. Algebraic Solving: A specific "exact" polynomial is constructed where the roots correspond to the jump locations. By using the decimated set, the system gains "algebraic leverage," making the root-finding process significantly more robust to the perturbations caused by the smooth parts of the function.
  4. Full Reconstruction: Once the jump locations ($\xi$) and magnitudes ($a$) are determined with high precision, the function is reconstructed by combining a piecewise polynomial (representing the jumps) with a truncated Fourier series (representing the smooth remainder).

Key Insights and Results

The primary contribution of this work is the formal proof and numerical demonstration that the $O(M^{-d-2})$ accuracy limit is achievable. By linking the problem to the stability of "confluent Prony systems," the author provides a rigorous error analysis showing that decimation minimizes the sensitivity of the reconstruction to the underlying smooth components of the signal.

Numerical simulations conducted in Mathematica validate these findings. Using synthetic piecewise-smooth functions with varying degrees of smoothness ($d=3, 4, 5, 7$), the "Full" decimated method significantly outperformed both the original Eckhoff method and earlier "half-order" iterations. At higher smoothness orders, the error reduction improved by several orders of magnitude, with the algorithm entering the asymptotic convergence regime much faster than its predecessors as the number of Fourier coefficients ($M$) increases.

Limitations and Future Work

Despite its theoretical success, the algorithm faces several practical hurdles:

  • A-priori Knowledge: The method requires prior knowledge of the number of discontinuities ($K$) and the smoothness parameter ($d$), which are often unknown in blind signal processing.
  • Noise Sensitivity: Achieving maximal convergence rates requires highly accurate high-frequency data. In fields like MRI or geophysics, these high-frequency coefficients are the most susceptible to noise.
  • Computational Complexity: Solving the underlying algebraic systems often requires high-precision arithmetic, which may limit the algorithm's utility in real-time engineering contexts.
  • Dimensionality: The current framework is strictly one-dimensional. Extending these algebraic techniques to 2D or 3D—essential for image processing and edge reconstruction—remains a significant open challenge.

Summary updated

Abstract

In this paper we provide a reconstruction algorithm for piecewise-smooth functions with a-priori known smoothness and number of discontinuities, from their Fourier coefficients, posessing the maximal possible asymptotic rate of convergence -- including the positions of the discontinuities and the pointwise values of the function. This algorithm is a modification of our earlier method, which is in turn based on the algebraic method of K.Eckhoff proposed in the 1990s. The key ingredient of the new algorithm is to use a different set of Eckhoff's equations for reconstructing the location of each discontinuity. Instead of consecutive Fourier samples, we propose to use a "decimated" set which is evenly spread throughout the spectrum.
BibTeX
@article{batenkov2015complete,
  author = {Dmitry Batenkov},
  title = {{Complete Algebraic Reconstruction of Piecewise-Smooth Functions from Fourier Data}},
  journal = {Math. Comput.},
  year = {2015},
  doi = {10.1090/s0025-5718-2015-02948-2},
}
Figure