The faster-than-fast Fourier transform

For a large range of practically useful cases, MIT researchers find a way to increase the speed of one of the most important algorithms in the information sciences.


Press Contact

Caroline McCall
Email: newsoffice@mit.edu
Phone: 617-253-2700
MIT News Office

Media Resources

1 images for download

Access Media

Media can only be downloaded from the desktop version of this website.

The Fourier transform is one of the most fundamental concepts in the information sciences. It’s a method for representing an irregular signal — such as the voltage fluctuations in the wire that connects an MP3 player to a loudspeaker — as a combination of pure frequencies. It’s universal in signal processing, but it can also be used to compress image and audio files, solve differential equations and price stock options, among other things.

The reason the Fourier transform is so prevalent is an algorithm called the fast Fourier transform (FFT), devised in the mid-1960s, which 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.

Best of 2012

At the Symposium on Discrete Algorithms (SODA) this week, a group of MIT researchers will present a new algorithm that, in a large range of practically important cases, improves on the fast Fourier transform. Under some circumstances, the improvement can be dramatic — a tenfold increase in speed. The new algorithm could be particularly useful for image compression, enabling, say, 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. A digital signal is just a series of numbers — discrete samples of an analog signal, such as the sound of a musical instrument. 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.

“Weighted” means that some of those frequencies count more toward the total than others. Indeed, many of the frequencies may have such low weights that they can be safely disregarded. That’s why the Fourier transform is useful for compression. An eight-by-eight block of pixels can be thought of as a 64-sample signal, and thus as the sum of 64 different frequencies. But as the researchers point out in their new paper, empirical studies show that on average, 57 of those frequencies can be discarded with minimal loss of image quality.

Heavyweight division

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. Indeed, if the signal is sparse enough, the algorithm can simply sample it randomly rather than reading it in its entirety.

“In nature, most of the normal signals are sparse,” says Dina Katabi, one of the developers of the new algorithm. Consider, for instance, a recording of a piece of chamber music: The composite signal consists of only a few instruments each playing only one note at a time. A recording, on the other hand, of all possible instruments each playing all possible notes at once wouldn’t be sparse — but neither would it be a signal that anyone cares about.

The new algorithm — which associate professor Katabi and professor Piotr Indyk, both of MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL), developed together with their students Eric Price and Haitham Hassanieh — relies on two key ideas. The first is to divide a signal into narrower slices of bandwidth, sized so that a slice will generally contain only one frequency with a heavy weight.

In signal processing, the basic tool for isolating particular frequencies is a filter. But filters tend to have blurry boundaries: One range of frequencies will pass through the filter more or less intact; frequencies just outside that range will be somewhat attenuated; frequencies outside that range will be attenuated still more; and so on, until you reach the frequencies that are filtered out almost perfectly.

If it so happens that the one frequency with a heavy weight is at the edge of the filter, however, it could end up so attenuated that it can’t be identified. So the researchers’ first contribution was to find a computationally efficient way to combine filters so that they overlap, ensuring that no frequencies inside the target range will be unduly attenuated, but that the boundaries between slices of spectrum are still fairly sharp.

Zeroing in

Once they’ve isolated a slice of spectrum, however, the researchers still have to identify the most heavily weighted frequency in that slice. 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.

Two University of Michigan researchers — Anna Gilbert, a professor of mathematics, and Martin Strauss, an associate professor of mathematics and of electrical engineering and computer science — had previously proposed an algorithm that improved on the FFT for very sparse signals. “Some of the previous work, including my own with Anna Gilbert and so on, would improve upon the fast Fourier transform algorithm, but only if the sparsity k” — the number of heavily weighted frequencies — “was considerably smaller than the input size n,” Strauss says. The MIT researchers’ algorithm, however, “greatly expands the number of circumstances where one can beat the traditional FFT,” Strauss says. “Even if that number k is starting to get close to n — to all of them being important — this algorithm still gives some improvement over FFT.”


Topics: Compression, Computer Science and Artificial Intelligence Laboratory (CSAIL), Computer science and technology, Electrical engineering and electronics, Fourier transforms, Signal processing

Comments

It will be many applications on fractals! (Mandelbrot asa...)
perhaps it will help you ? http://www.math.tugraz.at/Fractals09/talks/dutkay.pdf
The Sparse Fast Fourier Transform has a MIT web page: http://groups.csail.mit.edu/netmit/sFFT/ The paper mentioned in the article has also a direct document link, additionally to the abstract linked in the article: http://arxiv.org/PS_cache/arxiv/pdf/1201/1201.2501v1.pdf
I am pretty sure that the bottom signal is not a sum of the three above... And the transformation decomposes a signal into components rather that adding multiple signals.
I have been studying a mechanical effect with spring materials that relates to this article. My mathematics mentors have described the effect, that I have been working on, would be described by definition as a Fourier Transform of a Gaussian, which is also a Gaussian in the frequency space. If you would like more info on my applications please contact me at Lee Guthrie, kendrickguthrie@earthlink.net Lee Guthrie Quantum Springs
The proceedings papers from SODA is available on the SODA site. The meeting site is http://www.siam.org/meetings/da12/ The full SODA proceedings is at http://siam.omnibooksonline.com/2012SODA/index.html
* A bit more effort and they will reinvent the mpeg3 files which are based on finding the strongest frequencies and throwing away the ones close to them (if this paper is correct) * Not a word about how the method will work in 2D - any example of a decompressed image along with a Fourier-transform coded one? * Yes, the illustration is crap - couldn't they find someone who can handle Excel? I have the correct image but cannot join images.
Comment on image: Fourier transform is very important thing in undestanding of wave phenomenon (sinus function),because it enable us to explain a sophisticated wave as an adding of the basic waves component.
I had received helpful responses referencing Fourier and Laplace Transforms. The question I had asked was “Is there a formula that would describe the conversion of a Gaussian curve to a sine wave”. The mechanical process that I have been researching starts with a sheet spring material that is clamped at the ends to form the shape of a bell curve. In Euler's column theory this shape is formed by an axial compressive force greater than the first critical load used to produce the column's first deflection. I apply a transverse load to the length of the deflected material to produce the first sine wave with the length set by the end clamps. I continue to increase the transverse force to the low frequency wave to shift it to the next higher frequency wave with the corresponding lower amplitude and so on. This continues down till the yield strength of the material is passed. My process, compresses a linear material in two perpendicular directions. I can speculate compressing a round flat
<b><i>Editor's note: the image has been changed</i></b> <br /><br /> @madsh-- The illustration of Fourier transformation may not have been clear to you; however it is a common textbook illustration of Fourier transforms. I am pretty sure that the bottom signal is indeed the sum of the top three (we could check!) The point of the illustration is that the top three signals are pure "sinusoidal waves" with different frequencies, amplitudes and phases. When you add the three top sinewaves with different phases, amplitudes, and frequencies, you can get a signal that looks very different from any of the top three traces and, over the range sampled, appears somewhat random and non-repeating, in contrast to the top three traces. The point of the illustration is that an "arbitrary waveform" (such as the bottom waveform) can be represented as the weighted sum of a series of pure sine waves, a Fourier series. The illustration shows NO spectral information in the "frequency domain." This is probably what you found to be missing/confusing, or unexpected.
How this new technique compare with the wavelet transform?
Back to the top