Improved sparse Fourier approximation results: Faster implementations and stronger guarantees (Q2376358)

The problem of quickly estimating the best \(k\)-term Fourier representation for a given periodic function \(f:\;[0,2\pi]\to \mathbb C\) is studied. Solving this problem requires the identification of \(k\) of the largest magnitude Fourier series coefficients of \(f\) in worst case \(k^2\cdot\log^{O(1)}N\) time. Randomized sublinear-time Monte Carlo algorithms, which have a small probability of failing to output accurate answers for each input signal, have been developed for solving this problem (Gilbert et al. 2002, 2005). These methods were implemented as the Ann Arbor fast Fourier transform (AAFFT) and empirically evaluated by \textit{M. A. Iwen, A. Gilbert} and \textit{M. Strauss} [Commun. Math. Sci. 5, No. 4, 981--998 (2007; Zbl 1134.65093)]. In this paper, the authors present a new implementation, called the Gopher fast Fourier transform (GFFT), of more recently developed sparse Fourier transform techniques (cf. [\textit{M. A. Iwen}, Found. Comput. Math. 10, No. 3, 303--338 (2010; Zbl 1230.65145); Appl. Comput. Harmon. Anal. 34, No. 1, 57--82 (2013; Zbl 1260.65115)]). Experiments indicate that GFFT is faster than AAFFT.