The January 20, 2012 edition of ACM TechNews:
The Faster-Than-Fast Fourier Transform
MIT News (01/18/12) Larry Hardesty
Massachusetts Institute of Technology (MIT) researchers say they have developed an algorithm that improves on the fast Fourier transform (FFT). They say the algorithm could be particularly useful for image compression, enabling smartphones to wirelessly transmit large video files without draining their batteries or consuming their monthly bandwidth allotments. FFT takes a digital signal containing a certain number of samples and expresses it as the weighted sum of an equivalent number of frequencies. The new algorithm determines the weights of a signal’s most heavily weighted frequencies, and if the signal is sparse enough, the algorithm can sample it randomly instead of reading the entire signal. The researchers’ algorithm relies on dividing a signal into narrower slices of bandwidth, so that a slice will generally contain only one frequency with a heavy weight. The MIT researchers also developed a more efficient technique that borrows a signal-processing method from 4G cellular networks. The algorithm “greatly expands the number of circumstances where one can beat the traditional FFT,” says University of Michigan professor Martin Strauss.