A team of MIT researchers have developed a new algorithm that improves on the fast Fourier transform (FFT). The Fourier transform is a method for representing an irregular signal as a combination of pure frequencies. The new MIT algorithm is up to ten times faster than the traditional FFT algorithm. The MIT algorithm is useful for image compression and can enable smart phones to wirelessly transmit large video files without draining batteries or consuming monthly bandwidth allotments. The new MIT algorithm will be presented this week at the Association for Computing Machinery’s Symposium on Discrete Algorithms (SODA).
The new algorithm divides a digital signal (discrete sample of an analog signal) into narrower slices of bandwidth. The slices are sized so that a slice will generally contain only one frequency with a heavy weight. Weighted means that some of the frequencies are more important than others. The new algorithm determines the weights of a signal’s most heavily weighted frequencies. The fewer the number of heavily weighted frequencies, the greater the speedup the algorithm provides. If the signal is sparse enough (very small number of heavily weighted frequencies), the algorithm can just sample it randomly rather than reading it in its entirety.
In developing the new algorithm, one of the first issues the researchers had to deal with involved filters, which are used to isolate particular frequencies. Filters tend to have blurry boundaries. One range of frequencies will pass through the filter more or less intact, while frequencies just outside that range will be somewhat attenuated and frequencies outside that range will be attenuated still more until you reach the frequencies that are filtered out almost perfectly. If a frequency with a heavy weight is at the edge of the filter, then it could end up so attenuated that it can’t be identified. As a result, researchers had to find a computationally efficient way to combine filters so that they overlap. This ensures that no frequencies inside the target range will be unduly attenuated, while the boundaries between slices of spectrum are still fairly sharp.
Once a slice of spectrum have been isolated, the next step is to identify the most heavily weighted frequency in that slice. As explained in a paper the researchers will present at SODA, the identification can be performed by repeatedly cutting the slice of spectrum into smaller pieces and keeping only those in which most of the signal power is concentrated.
In a currently unpublished paper, the MIT researchers describe a much more efficient technique that 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.
The new algorithm was developed by Katabi and Piotr Indyk, both professors in MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL), and their students Eric Price and Haitham Hassanieh.
More info: Massachusetts Institute of Technology