The Fourier transformation is arguably the most important algorithm in information technology, with immense applications as well in optics, signal and image processing, pattern recognition etc. Thanks to this remarkable mathematical operation, we’re able to see videos or listen to music on an iPod, as it turns the digital information into readable frequencies. Recently, MIT scientists have managed to come up with an optimized algorithm of the Fast Fourier Transformation, which was already fast enough as one can imagine. The researchers’ results in some instances had a tenfold increase in processing speed.
In simple terms the Fourier transformation turns signals into frequencies. A simple example as far as applications go is how it can turn voltage signals transmitted through a wire to an mp3 player into sounds rendered through a speaker fast and easy. However, it’s been found indispensable in applications ranging from economics, engineering, sociology and so on.
In the 1960s the Fast Fourier Transformation algorithm was developed, which provided an absolute breakthrough, still the question remained to this day whether it could be optimized even further. The MIT mathematicians devised the new faster than Fast Fourier Transformation by granting importance to frequencies that “weigh” more and overlooking weak signals.
The algorithm takes a digital signal containing a certain number of samples and expresses it as the weighted sum of an equivalent number of frequencies. Some of these frequencies are more important or “heavy” to the signal, and are thus prioritized. The algorithm slices the signal into narrow bandwidths, each slice containing just one heavy frequency. Each slice is then sliced again and so on once even further until low-weighted frequencies and highly-weighted signals are completely isolated from one another.
In “spare” signals, whose Fourier transforms include a relatively small number of heavily weighted frequencies, the new algorithm can output at lightning speed compared to the old one, as low weight signals are cut out completely with absolutely no loss in quality. “In nature, most of the normal signals are sparse,” says Dina Katabi, one of the developers of the new algorithm.
Considering most of the signals in nature are sparse, and the fact that the FFT was already lightning fast, this new improvement from MIT might have extraordinary consequences. Using your smartphone to wirelessly transmit large video files without draining the battery is just one application, out of countless that might benefit from it.
Read more about the research in technical detail at the MIT press release.