What is the sparse Fourier transform?

Question

MIT has been making a bit of noise lately about a new algorithm that is touted as a faster Fourier transform that works on particular kinds of signals, for instance: "Faster Fourier transform named one of world’s most important emerging technologies". The MIT Technology Review magazine says:

With the new algorithm, called the sparse Fourier transform (SFT), streams of data can be processed 10 to 100 times faster than was possible with the FFT. The speedup can occur because the information we care about most has a great deal of structure: music is not random noise. These meaningful signals typically have only a fraction of the possible values that a signal could take; the technical term for this is that the information is "sparse." Because the SFT algorithm isn't intended to work with all possible streams of data, it can take certain shortcuts not otherwise available. In theory, an algorithm that can handle only sparse signals is much more limited than the FFT. But "sparsity is everywhere," points out coinventor Katabi, a professor of electrical engineering and computer science. "It's in nature; it's in video signals; it's in audio signals."

Could someone here provide a more technical explanation of what the algorithm actually is, and where it might be applicable?

EDIT: Some links:

• The paper: "Nearly Optimal Sparse Fourier Transform" (arXiv) by Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price.
• Project website - includes sample implementation.

Answer 1

The idea of the algorithm is this: assume you have a length $N$ signal that is sparse in the frequency domain. This means that if you were to calculate its discrete Fourier transform, there would be a small number of outputs $k \ll N$ that are nonzero; the other $N-k$ are negligible. One way of getting at the $k$ outputs that you want is to use the FFT on the entire sequence, then select the $k$ nonzero values.

The sparse Fourier transform algorithm presented here is a technique for calculating those $k$ outputs with lower complexity than the FFT-based method. Essentially, because $N-k$ outputs are zero, you can save some effort by taking shortcuts inside the algorithm to not even generate those result values. While the FFT has a complexity of $O(n \log n)$, the sparse algorithm has a potentially-lower complexity of $O(k \log n)$ for the sparse-spectrum case.

For the more general case, where the spectrum is "kind of sparse" but there are more than $k$ nonzero values (e.g. for a number of tones embedded in noise), they present a variation of the algorithm that estimates the $k$ largest outputs, with a time complexity of $O(k \log n \log \frac{n}{k})$, which could also be less complex than the FFT.

According to one graph of their results (reproduced in the image below), the crossover point for improved performance with respect to FFTW (an optimized FFT library, made by some other guys at MIT) is around the point where only $\frac{1}{2^{11}}$-th to $\frac{1}{2^{10}}$-th of the output transform coefficients are nonzero. Also, in this presentation they indicate that the sparse algorithm provides better performance when $\frac{N}{k} \in [2000, 10^6]$.

These conditions do limit the applicability of the algorithm to cases where you know there are likely to be few significantly-large peaks in a signal's spectrum. One example that they cite on their Web site is that on average, 8-by-8 blocks of pixels often used in image and video compression are almost 90% sparse in the frequency domain and thus could benefit from an algorithm that exploited that property. That level of sparsity doesn't seem to square with the application space for this particular algorithm, so it may just be an illustrative example.

I need to read through the literature a bit more to get a better feel for how practical such a technique is for use on real-world problems, but for certain classes of applications, it could be a fit.

Answer 2

I have looked through the paper and I think I got the general idea of the method. The "secret souse" of the method is how to get sparse representation of input signal in frequency domain. The previous algorithms used kind of brute force for location of dominant sparse coefficient. This method use instead technique which called "space recovery" or "compressed sensing" wiki article is here The exact method of sparse recovery used here looks similar to 'hard thresholding" - one of the dominant sparse recovery methods.

PS technique of sparse recovery/compressed sensing and connected to it L1 minimization used a lot in modern signal processing and especially in connection with Fourier transform. In fact it's a must to know for modern signal processing. But before Fourier transform was used as one of the methods for solution of sparse recovery problem. Here we see opposite - sparse recovery for Fourier transform.

Good site for overview compressed sensing: nuit-blanche.blogspot.com/

PPS answer to previous comment - if input signal is not exactly sparse it's lossy.

Feel free to correct me if I got method wrong.

Answer 3

I haven't read the paper on sFFT, but my feeling is that the idea of fasten the FFT behind is exploiting the prior of k-sparsity. Hence, one do not have to compute all entries of FFT coefficients, instead, only computing k of them. So that's why for k-sparse signal, the complexity is O(klog n) instead of O(nlog n) for conventional FFT.

Any way, regarding to the comments of @rcmpton, by saying "The idea behind compressed sensing is that you can recover sparse data from sparse random samples drawn from a different domain (eg recover sparse images from random sparse frequency data (ie MRI))." The question is what is "sparse random samples"? I think it might be samples collected by randomly projecting the sparse data to some lower (measurement) subspace.

And as I understood, the theoretical framework of compressive sensing is majorly comprised of 3 issues, sparsity, measurement, and recovery. By sparsity, it pertains to seeking sparse representations for certain class of signals, which is the task of dictionary learning. By measurement, it pertains to seeking a efficient way (computational efficiency and recoverable) to measure the data (or projecting data to lower measurement space), which is the task of measurement matrix design, such as random Gaussian matrix, structured random matrix, .... And by recovery, is the sparse regularized linear inversion problems, l0, l1, l1-l2, lp, l-group, blabla..., and the resulted algorithms are various, Matching pursuit, soft thresholding, hard thresholding, basis pursuit, bayesian, ....

It is true that "cs is minimization of L1 norm", and L1 norm is a basic principle for cs, but cs is not only minimization of L1 norm. Besides the above 3 parts, there are also some extensions, like structured (group, or model) compressive sensing, where structured sparsity is also exploited, and is proved to largely improve the recovery ability.

As a conclusion, cs is a big step in sampling theory, providing an efficient way to sample signals, provided that these signals are sparse enough. So, cs is a sampling theory, anyone who is going to use it as some technique for classification or recognition is misleading the principle. And occasionally, I find some paper titled with "compressive sensing based .....", and I think the principle of such paper is exploiting l1-minimization instead of cs and it's better to use "l1-minimization based ....".

If I am wrong, correct me please.

Answer 4

I've looked into Sparse Fourier Transform. I've found that it's just grouping data points before running them through a shorter FFT than what you normally would use. Unfortunately, if your data is signal + noise, this has the side-effect of raising the noise floor.