You don’t need to get too far into signal processing before you encounter FFTs or Fast Fourier Transforms. The Fourier transform shows how a complex waveform can be described as a sum of fundamental waveforms. Researchers have been trying since the 1960s to find a better, less computationally intensive method to achieve the same goal. 

  

Last year MIT researchers including Piotr Indyk and Dina Katabi (photo) did just that, unveiling an algorithm that in some circumstances can perform Fourier transforms hundreds of times more quickly than the traditional 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.

 

In a paper to be 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.