Quantitative estimates: How well does the discrete Fourier transform approximate the Fourier transform on R

Martin Ehler, Karlheinz Gröchenig, Andreas KlotzarXiv 2024 · DOI · arXiv

Introduction

In modern signal processing and numerical analysis, the Fast Fourier Transform (FFT) is an indispensable tool used to approximate the continuous Fourier transform. Despite its ubiquity, a rigorous mathematical foundation providing sharp, quantitative error estimates for functions with varying decay rates has been largely missing. This paper addresses this gap by deriving explicit error bounds for approximating the continuous Fourier transform using the Discrete Fourier Transform (DFT) for functions characterized by polynomial or sub-exponential decay.

The Approximation Challenge

Calculating the Fourier transform on a computer necessitates two fundamental approximations of a continuous signal:

  1. Truncation: The signal must be cut off at a finite window of length $p$.
  2. Discretization: The signal must be sampled at discrete points with a spacing of $h$.

For functions with compact support—those that are zero outside a specific range—the error is well-understood. However, most physical signals, such as Gaussians or decaying exponentials, are not compactly supported. Previous theoretical attempts to bound errors for these signals often relied on restrictive boundary conditions that do not reflect practical applications. This mismatch often resulted in "theoretical gaps" where numerical experiments outperformed mathematical predictions. This research closes these gaps by providing a framework that accounts for both local smoothness and global decay.

Methodology: Bridging the Continuous and Discrete

The authors utilize a sophisticated mathematical framework to provide explicit constants for error estimation, moving beyond the limitations of standard "big-O" notation. Key components of their approach include:

  • Wiener Amalgam Spaces: These function spaces serve as the primary technical tool, allowing the authors to simultaneously track local smoothness (which influences discretization error) and global decay (which influences truncation error).
  • Time-Frequency Symmetry: By treating time and frequency as symmetric dimensions and applying the Poisson Summation Formula, the authors decompose the total error into a "time component" (truncation error) and a "frequency component" (aliasing or discretization error).
  • Explicit Constants: Unlike purely asymptotic studies, this paper derives specific constants, making the estimates directly applicable for practitioners who need to determine the error for a specific number of samples $n$.

The $f^{a,b}$ Synthetic Benchmark

To verify the sharpness of their theoretical bounds, the authors developed a new synthetic benchmark family of functions denoted as $f^{a,b}$. These functions are constructed using infinite linear combinations of B-splines and possess exact, known polynomial decay in both time ($a$) and frequency ($b$). Because their Fourier transforms can be calculated analytically, these functions allow for a precise comparison between theoretical error bounds and actual numerical results, proving that the derived bounds cannot be improved.

Key Insights and the "Optimal Recipe"

The research yields several critical insights into the behavior of the DFT:

The Balancing Act

The total error in the approximation is essentially the sum of two terms: $p^{-\alpha}$ (truncation) and $h^\beta$ (discretization). To achieve the minimum error for a fixed number of samples $n$, these two terms must be balanced.

The Failure of the $\sqrt{n}$ Heuristic

A common engineering rule of thumb is to set the window length $p = \sqrt{n}$ and spacing $h = 1/\sqrt{n}$. The authors demonstrate that this is only optimal if the signal's decay rate in time exactly matches its decay rate in frequency. For signals that are very smooth but decay slowly, a much larger window and coarser spacing are required to maintain accuracy.

Boundary Conditions

Previous literature suggested that discontinuities at the edges of the sampling window ($f(-p/2) \neq f(p/2)$) would lead to high error rates. This paper proves that by employing the correct sampling strategy, high-order convergence can be achieved regardless of these boundary jumps.

Results and Efficiency Gains

The paper provides an "optimal recipe" for sampling: for a function with time decay $\alpha$ and frequency decay (smoothness) $\beta$, the optimal sampling rate is $h \approx n^{-\alpha/(\alpha+\beta)}$.

In numerical experiments, this optimal strategy demonstrated significant efficiency gains. For example, to reach a target accuracy of $10^{-5}$, the optimal recipe required only $2^{12}$ (4,096) samples. In contrast, the standard $\sqrt{n}$ approach required $2^{17}$ (131,072) samples. This represents a 32x reduction in data required to achieve the same level of precision.

Limitations and Future Directions

While the paper provides a robust foundation for $L^2$ (average) error estimates, several areas remain for future exploration:

  • Sinc Interpolation: The proof for convergence using sinc interpolation remains incomplete because the sinc function is not absolutely summable.
  • Pointwise Accuracy: The tools used are optimized for the $L^2$ norm; while pointwise estimates are provided, they may not be the tightest possible bounds for single-point accuracy.
  • Non-uniform Grids: The current study is restricted to equispaced sampling, leaving the challenge of quantitative estimates for non-uniform grids to future research.

Summary updated

BibTeX
@misc{ehler2024quantitative,
  author = {Martin Ehler and Karlheinz Gröchenig and Andreas Klotz},
  title = {{Quantitative estimates: How well does the discrete Fourier transform approximate the Fourier transform on R}},
  year = {2024},
  eprint = {2403.03810},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2403.03810},
}
Figure