MIT researchers have found a way to increase the speed of one of the most important algorithms in the information sciences: the Fourier Transform. It’s a method for representing an irregular signal as a combination of pure frequencies. It’s universal in signal processing, but it can also be used to compress image and audio files, and solve differential equations.
An algorithm called the fast Fourier transform (FFT), devised in the mid-1960s, made it practical to calculate Fourier transforms on the fly. Ever since the FFT was proposed, however, people have wondered whether an even faster algorithm could be found. MIT researchers have created a new algorithm that, in a large number of cases, improves on the fast Fourier transform. Under some circumstances, the improvement can be a tenfold increase in speed.
The new 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. Like the FFT, the new algorithm works on digital signals. The FFT takes a digital signal containing a certain number of samples and expresses it as the weighted sum of an equivalent number of frequencies.
Signals whose Fourier transforms include a relatively small number of heavily weighted frequencies are called “sparse.” The new algorithm determines the weights of a signal’s most heavily weighted frequencies; the sparser the signal, the greater the speedup the algorithm provides.
