On the Numerical Stability of Fourier Extensions

Ben Adcock, Daan Huybrechs, Jesús Martín-Vaquero

TL;DR

This paper investigates Fourier extensions, a powerful technique for approximating analytic functions. It demonstrates that despite the underlying ill-conditioned linear systems, Fourier extensions are surprisingly numerically stable in finite precision, achieving at least superalgebraic convergence. Furthermore, it shows how these extensions can overcome theoretical barriers related to approximating functions from equispaced data, offering a stable and efficient approach.

What Problem Does This Paper Address?

Approximating functions, especially non-periodic analytic ones, is a fundamental task in numerical analysis. Fourier series are excellent for periodic functions, offering fast convergence and high resolution. However, extending this to non-periodic functions on a bounded interval typically leads to the Gibbs phenomenon and slow convergence. Fourier extensions offer a solution by using a larger domain for the Fourier series, restoring good convergence properties. The challenge arises because computing these extensions involves solving ill-conditioned linear systems, which usually implies that finite-precision computations would destroy the theoretical accuracy. This paper addresses the question of whether this ill-conditioning actually hinders the practical performance of Fourier extensions. Additionally, it tackles the problem of recovering functions from equispaced data, where theoretical results suggest a trade-off between stability and convergence speed.

Methods

The paper analyzes two main types of Fourier extensions: continuous and discrete. The core idea is to approximate a function $f$ on $[-1,1]$ by a Fourier series on a larger interval $[-T,T]$.

  • Continuous Fourier Extension (FE): This is formulated as a least-squares problem, finding the best approximation in a subspace of Fourier modes.
  • Discrete Fourier Extension: This is a practical adaptation of the continuous FE, using a finite set of equispaced or specially chosen (e.g., Chebyshev) nodes for the least-squares problem.
  • Equispaced Fourier Extension: This specifically addresses the challenge of using data sampled at equispaced points.

The analysis relies heavily on:

  • Frame Theory: The Fourier basis is treated as a frame, which explains the potential for ill-conditioning due to redundancy.
  • Polynomial Approximation Theory: By transforming variables (e.g., using $y = \cos x$), Fourier extensions can be related to polynomial approximations, allowing the use of established theoretical tools.
  • Singular Value Decomposition (SVD): The paper uses SVD to analyze the behavior of numerical solvers and to understand the impact of small singular values on the approximation.
  • Potential Theory: Used to analyze the Runge phenomenon and the behavior of equispaced nodes.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and numerical examples using synthetic functions.

Key Insights and Ideas

  • Ill-conditioning doesn't kill accuracy: The most surprising finding is that despite the exponentially ill-conditioned matrices involved in computing Fourier extensions, the numerical extensions themselves are remarkably stable and achieve good accuracy in finite precision. This is because the error in the coefficients doesn't translate directly into a large error in the function approximation on the original domain.
  • Frames and Redundancy: The Fourier basis is a frame, meaning it's redundant. This redundancy is the root cause of the ill-conditioning in the coefficient space, but it also allows for multiple ways to represent a function, some of which are better suited for numerical computation.
  • Circumventing Theoretical Barriers: For equispaced data, a theoretical result states that exponential convergence implies exponential ill-conditioning. The paper shows that Fourier extensions, particularly with oversampling, can achieve stable and rapid convergence, effectively sidestepping this strict barrier by not strictly adhering to the conditions under which the theorem applies.
  • Breakpoint Behavior: Numerical Fourier extensions exhibit a "breakpoint" behavior. For smaller truncation parameters ($N$), they converge geometrically (like exact extensions). Beyond this breakpoint, convergence becomes superalgebraic, eventually limited by machine precision.

Key Results

  • Numerical Stability: Fourier extensions (continuous, discrete, and equispaced) are shown to be numerically stable in finite precision, with condition numbers that are bounded or grow much slower than expected from the exact problem.
  • Superalgebraic Convergence: Numerical Fourier extensions achieve at least superalgebraic convergence, meaning their error decreases faster than any fixed power of $1/N$.
  • Equispaced Data Advantage: Equispaced Fourier extensions, especially with oversampling, provide a stable method for approximating functions from equispaced data, achieving good convergence rates.
  • Maximal Accuracy: Numerical continuous FEs are limited to approximately $\sqrt{\epsilon_{mach}}$ accuracy, while discrete and equispaced FEs can reach close to machine precision $\epsilon_{mach}$.

Limitations and Future Work

  • Theoretical Bounds for Equispaced FEs: While numerical evidence strongly suggests that linear oversampling ($M = \gamma N$) is sufficient for stable equispaced FEs, a rigorous proof for the boundedness of the relevant constants ($C_1, C_2$) is still lacking.
  • Choosing Parameters: While practical choices for parameters like $T$ and $\gamma$ are suggested, a more formal understanding of their optimal selection for various problem types (e.g., oscillatory functions) could be beneficial.
  • Generalization to Non-Analytic Functions: The analysis primarily focuses on analytic functions. Extending these results to functions with finite regularity would be valuable.
  • Understanding the Prolate Matrix Connection: The paper notes the connection of the FE matrices to prolate spheroidal matrices. A deeper analysis of this connection, particularly for the equispaced case, could lead to further insights.

Summary updated

Abstract

An effective means to approximate an analytic, nonperiodic function on a bounded interval is by using a Fourier series on a larger domain. When constructed appropriately, this so-called Fourier extension is known to converge geometrically fast in the truncation parameter. Unfortunately, computing a Fourier extension requires solving an ill-conditioned linear system, and hence one might expect such rapid convergence to be destroyed when carrying out computations in finite precision. The purpose of this paper is to show that this is not the case. Specifically, we show that Fourier extensions are actually numerically stable when implemented in finite arithmetic, and achieve a convergence rate that is at least superalgebraic. Thus, in this instance, ill-conditioning of the linear system does not prohibit a good approximation.In the second part of this paper we consider the issue of computing Fourier extensions from equispaced data. A result of Platte et al. (SIAM Rev. 53(2):308–318, 2011) states that no method for this problem can be both numerically stable and exponentially convergent. We explain how Fourier extensions relate to this theoretical barrier, and demonstrate that they are particularly well suited for this problem: namely, they obtain at least superalgebraic convergence in a numerically stable manner.
BibTeX
@inproceedings{adcock2014numerical,
  author = {Ben Adcock and Daan Huybrechs and Jesús Martín-Vaquero},
  title = {{On the Numerical Stability of Fourier Extensions}},
  booktitle = {Found. Comput. Math},
  year = {2014},
  url = {https://openreview.net/forum?id=bVo3qVDroU3},
}
Figure