Faster, faster, Fourier transform

Tech and Computer : A new and faster Fourier transform algorithm has been developed by Dina Katabi of MIT and colleagues. The Fourier transform is a method for representing an irregular signal as a combination of pure frequencies. It’s used in a wide variety of applications, including nuclear magnetic resonance imaging, image and audio file compression, and the solving of differential equations. The fast Fourier transform (FFT) technique, which was developed in the 1960s, made it practical to calculate Fourier transforms on the fly; it 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 the frequencies count more toward the sum than others, and many of the frequencies may have such low weights that they can be safely ignored, which is why the Fourier transform is useful for compression. The new algorithm determines the weights of a signal’s most heavily weighted frequencies; the fewer such frequencies in the signal, the greater the increase in speed the algorithm provides.