Parameter selection and numerical approximation properties of Fourier extensions from fixed data

Ben Adcock, Joseph Ruan

TL;DR

Fourier extensions (FEs) are a powerful tool for approximating non-periodic functions, but choosing the right parameters—the extension ratio $T$ and oversampling ratio $\eta$—has long been a source of confusion. This paper demonstrates that if you fix your desired numerical stability (condition number), the specific choice of $T$ has almost no impact on accuracy, justifying the use of $T=2$ to leverage existing fast algorithms.

What Problem Does This Paper Address?

Approximating a smooth, non-periodic function from discrete data points is a classic challenge in numerical analysis. Standard Fourier series suffer from the Gibbs phenomenon (oscillations near boundaries), while polynomial interpolation on equispaced grids is notoriously unstable due to the Runge phenomenon.

Fourier extensions circumvent these issues by approximating the function on a physical interval $[-1, 1]$ using a Fourier series defined on a larger "extended" domain $[-T, T]$. However, this introduces two "tuning knobs":

  1. The extension parameter ($T$): The ratio of the extended domain to the physical domain.
  2. The oversampling ratio ($\eta$): The number of data points per Fourier mode.

Previously, researchers struggled to find the "optimal" $T$. A small $T$ (close to 1) offers better resolution for oscillations but requires massive oversampling to remain stable. A large $T$ is more stable but offers poorer resolution. The authors set out to find if there is a "sweet spot" or if the parameters are more flexible than previously thought.

Methods

The authors conduct an extensive numerical investigation into the stability and accuracy of FEs. Key aspects of their approach include:

  • Stability-Fixed Comparison: Instead of comparing arbitrary pairs of $(T, \eta)$, they fix a maximum allowable condition number ($\kappa^*$) and then numerically determine the maximum number of Fourier modes ($N$) that can be used for a given data size ($M$) without exceeding that stability limit.
  • Regularized Solvers: They primarily use Truncated Singular Value Decomposition (SVD) to solve the underlying least-squares problem, which is inherently ill-conditioned. They also test "black-box" solvers like Matlab’s backslash operator.
  • Resolution Power Analysis: They define and measure "points-per-wavelength" to quantify how many samples are needed to capture high-frequency oscillations.

Datasets

While not a "dataset" in the machine learning sense, the authors evaluate their findings against a diverse suite of nine test functions ($f_1$ through $f_9$). These include:

  • Highly oscillatory exponentials and sine waves.
  • Functions with singularities in the complex plane near the interval (e.g., Runge-like functions).
  • The Airy function and "flat" functions that lack analyticity.

They also test different data distributions: equispaced, jittered (noisy) pointwise samples, logarithmic distributions, and Fourier coefficients.

Key Insights and Ideas

  • The Invariance Phenomenon: The most striking finding is that for a fixed condition number, the choice of $T$ is largely irrelevant to the final approximation error. The benefits of a smaller $T$ are exactly offset by the requirement for a larger oversampling ratio $\eta$ to maintain stability.
  • Saturation Points: There is a limit to this invariance. If $T$ is chosen too large, the system becomes "too stable" (saturation), preventing the algorithm from utilizing the full "budget" of the allowed condition number, which eventually degrades accuracy.
  • Resolution Power Formula: The authors establish that the resolution constant (the number of points needed per wavelength) is approximately $r \approx T\eta$.
  • Precision vs. Resolution: Interestingly, using a higher SVD tolerance (lower precision) allows for a higher number of modes $N$ for the same data size $M$. This means if you only need 3-6 digits of accuracy, you can resolve much higher frequencies with fewer data points.

Key Results

  • Validation of $T=2$: Since the choice of $T$ doesn't significantly affect accuracy (outside of saturation), the authors conclude that $T=2$ is the most practical choice. This is significant because $T=2$ allows for a fast algorithm (developed by M. Lyon) that runs in $O(M \log^2 M)$ time.
  • Stability Trade-offs: For equispaced data, they show that increasing the oversampling ratio $\eta$ beyond 2.0 yields diminishing returns in stability.
  • Data Robustness: The "invariance" of $T$ holds true for equispaced, jittered, and Fourier data, suggesting it is a fundamental property of the Fourier extension method rather than an artifact of a specific grid.

Limitations and Future Work

  • Lack of Formal Proof: The conclusions are based on rigorous numerical experiments. The authors acknowledge that a formal mathematical proof—likely involving an intricate analysis of singular values related to Slepian’s prolate matrix—is still missing.
  • Dimensionality: The study is confined to 1D approximations. Extending these insights to higher-dimensional Fourier extensions on complex geometries remains an open area.
  • Dynamic Parameter Selection: The paper suggests it might be possible to vary $T$ dynamically with the data size $M$ to further optimize resolution, a direction they leave for future research.

Summary updated

Abstract

Fourier extensions have been shown to be an effective means for the approximation of smooth, nonperiodic functions on bounded intervals given their values on an equispaced, or in general, scattered grid. Related to this method are two parameters. These are the extension parameter $T$ (the ratio of the size of the extended domain to the physical domain) and the oversampling ratio $η$ (the number of sampling nodes per Fourier mode). The purpose of this paper is to investigate how the choice of these parameters affects the accuracy and stability of the approximation. Our main contribution is to document the following interesting phenomenon: namely, if the desired condition number of the algorithm is fixed in advance, then the particular choice of such parameters makes little difference to the algorithm's accuracy. As a result, one is free to choose $T$ without concern that it is suboptimal. In particular, one may use the value $T=2$ - which corresponds to the case where the extended domain is precisely twice the size of the physical domain - for which there is known to be a fast algorithm for computing the approximation. In addition, we also determine the resolution power (points-per-wavelength) of the approximation to be equal to $T η$, and address the trade-off between resolution power and stability.
BibTeX
@article{adcock2014parameter,
  author = {Ben Adcock and Joseph Ruan},
  title = {{Parameter selection and numerical approximation properties of Fourier extensions from fixed data}},
  journal = {Journal of Computational Physics},
  year = {2014},
  url = {https://openreview.net/forum?id=updVkqtlDD},
}
Figure