Leaner Fourier Transforms

Piotr Indyk, Dina Katabi, Eric Price, and
Haitham Hassanieh (left to right)

Leaner Fourier Transforms

Leaner Fourier transforms - MIT News Office

A Faster Fourier Transform - MIT Technology Review

MIT's new algorithm could solve thorny optimization problems - Computerworld 

Sparse FFT Code

Ever since its development in the 1960s by Cooley and Tukey, computer scientists have been searching for an algorithm to better the FFT. Last year MIT researchers Piotr Indyk and Dina Katabi did just that, unveiling an algorithm that in some circumstances can perform Fourier transforms hundreds of times more quickly than the fast Fourier transform (FFT).

Now Indyk, a professor of computer science and engineering and a member of the Theory of Computation Group within the Computer Science and Artificial Intelligence Laboratory (CSAIL), and his team have gone a step further, significantly reducing the number of samples that must be taken from a given signal in order to perform a Fourier transform operation.

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 a paper presented at the ACM-SIAM Symposium on Discrete Algorithms in January, Indyk, postdoc Michael Kapralov, and former student Eric Price will reveal an algorithm that can perform Fourier transforms using close to the theoretical minimum number of samples. They have also bettered even this, developing an algorithm that uses the minimum possible number of signal samples.

This could significantly reduce the time it takes medical devices such as magnetic resonance imaging (MRI) and nuclear magnetic resonance (NMR) machines to scan patients, or allow astronomers to take more detailed images of the universe, Indyk says.