Fourier Sampling and Beyond

The Fast Fourier Transform (FFT) is a fundamental algorithm that computes the Discrete Fourier Transform of an n-dimensional signal in O(n log n) time. It is unknown whether the running time can be improved in general. However, in applications such as image, audio, and video compression where the output is “sparse” (i.e., k n coordinates are “large” and contain most of the energy), it is possible to estimate the large coordinates in less than O(n log n) time. We show the first algorithms that achieve this for any k = o(n).

The sparse Fourier transform problem lies in the broader area of sparse recovery or compressive sensing. This area considers the robust recovery of a sparse vector x from relatively few linear measurements Ax, and has applications in diverse settings such as streaming algorithms, camera design, and genetic testing. We discuss multiple extensions to the sparse recovery framework, including a proof that the number of measurement can be improved – in some cases exponentially – if the measurements are chosen adaptively.