Fourier Sampling and Beyond


January 14, 2013


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.


Eric Price

Eric Price is currently finishing his PhD at MIT under the supervision of Piotr Indyk. He received Bachelor’s degrees in Computer Science and Mathematics from MIT. His research interests include sparse recovery and information theory. Eric received a 2009 NSF Graduate Research Fellowship and a 2012 Simons Graduate Fellowship.