sFFT: Sparse Fast Fourier Transform

Remember the new FFT algorithm out of MIT that uses the sparsity of the signal to perform a Faster FFT ? Well, the authors (Dina Katabi, Piotr Indyk, Haitham Hassanieh, Eric Price), just set up a website that will  now eventually hosts an implementation of it. ( Piotr  tells me it should be up after the news storm has settled down). The KIHP sFFT page currently starts with:

IntroductionWe consider the sparse Fourier transform problem: given a complex vector x of length n, and a parameter k, estimate the k largest (in magnitude) coefficients of the Fourier transform of x. The problem is of key interest in several areas, including signal processing, audio/image/video compression, and learning theory. We propose a new algorithm for this problem. The algorithm leverages techniques from digital signal pro- cessing, notably Gaussian and Dolph-Chebyshev filters. The resulting algorithm is structurally simpler than its predecessors. As a consequence, we are able to extend considerably the range of sparsity, k, for which the algorithm is faster than FFT, both in theory and practice.

---

Algorithm

Algorithm		Complexity		Sparsity Range
sFFT 1.0 (Non-Iterative Alghorithm)	::
sFFT 2.0 (sFFT 1.0 + Heuristic)	::
sFFT 3.0 (Exact k Sparse Algorithm)	::
sFFT 4.0 (General k Sparse Algorithm)	::
Lower Bound	::

The figure of deep interest is here I think with a comparison with the Fastest Fourier Transform in the West. (FFTW)

The paper presented at SODA is Simple and Practical Algorithm for Sparse Fourier Transform by  Haitham Hassanieh ,  Piotr Indyk  , Dina Katabi, and  Eric Price. The abstract reads:

 . We consider the sparse Fourier transform problem: given a complex vector x of length n, and a parameter k, estimate the k largest (in magnitude) coefficients of the Fourier transform of x. The problem is of key interest in several areas, including signal processing, audio/image/video compression, and learning theory. We propose a new algorithm for this problem. The algorithm leverages techniques from digital signal processing, notably Gaussian and Dolph-Chebyshev filters. Unlike the typical approach to this problem, our algorithm is not iterative. That is, instead of estimating “large” coefficients, subtracting them and recursing on the reminder, it identifies and estimates the k largest coefficients in “one shot”, in a manner akin to sketching/streaming algorithms. The resulting algorithm is structurally simpler than its predecessors. As a consequence, we are able to extend considerably the range of sparsity, k, for which the algorithm is faster than FFT, both in theory and practice.

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.