Fast Algorithms for the Computation of Fourier Extensions of Arbitrary Length

Fourier series of smooth, nonperiodic functions on $[-1,1]$ are known to exhibit the Gibbs phenomenon, and they 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 to converge at least superalgebraically in the truncation parameter $N$. A fast $\mathcal{O}(N\log^2N)$ 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^2N)$ 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 ...