At the upcoming ACM Symposium on Discrete Algorithms conference, a group of MIT researchers is presenting a new Fourier Transform algorithm that can improve on the now-standard “Fast Fourier Transform” (FFT) algorithm by a full order of magnitude.
In the SODA paper, they do this by repeatedly cutting the slice of spectrum into smaller pieces and keeping only those in which most of the signal power is concentrated. But in an as-yet-unpublished paper, they describe a much more efficient technique, which borrows a signal-processing strategy from 4G cellular networks. Frequencies are generally represented as up-and-down squiggles, but they can also be though of as oscillations; by sampling the same slice of bandwidth at different times, the researchers can determine where the dominant frequency is in its oscillatory cycle.
Their work is based on some previously found optimizations, but expands them to a significantly larger opportunity base. The FFT is the foundation of many digital signal algorithms like MP3 and image compression codecs. This new optimization could bring them to a whole new class of devices like mobiles and tablets, all while decreasing battery consumption.
