< Back to previous page

Publication

Fast algorithms for the computation of Fourier extensions of arbitrary length

Journal Contribution - Journal Article

Fourier series of smooth, non-periodic functions on $[-1,1]$ are known to exhibit the Gibbs phenomenon, and exhibit overall slow convergence. One way of overcoming these problems is by using a Fourier series on a larger domain, say $[-T,T]$ with $T>1$, a technique called Fourier extension or Fourier continuation. When constructed as the discrete least squares minimizer in equidistant points, the Fourier extension for analytic functions has been shown shown to converge at least superalgebraically in the truncation parameter $N$. A fast ${\mathcal O}(N \log^2 N)$ algorithm has been described to compute Fourier extensions for the case where $T=2$, compared to ${\mathcal O}(N^3)$ for solving the dense discrete least squares problem. We present two ${\mathcal O}(N\log^2 N )$ algorithms for the computation of these approximations for the case of general $T$, made possible by exploiting the connection between Fourier extensions and Prolate Spheroidal Wave theory. The first algorithm is based on the explicit computation of so-called periodic discrete prolate spheroidal sequences, while the second algorithm is purely algebraic and only implicitly based on the theory.
Journal: SIAM Journal on Scientific Computing
ISSN: 1064-8275
Issue: 2
Volume: 38
Pages: A899 - A922
Publication year:2016
BOF-keylabel:yes
IOF-keylabel:yes
BOF-publication weight:2
CSS-citation score:2
Authors from:Higher Education
Accessibility:Closed