Faster Fourier Transforms

January 23, 2012

Butterflies make multiple appearances in science and technology. There is, of course the flying insect of the order, Lepidoptera. Surprisingly, "Lepidoptera" and "Coleoptera" are part of the dialog of a Jerry Lewis movie, Three on a Couch (1966, Jerry Lewis, Director). Rutherford, an archetypal nerd and one of Lewis' four characters in this movie, lectures one of the female leads on their characteristics.[1]

The engineers and experimentalists among my readership will be familiar with the butterfly valve. I worked for a time on high temperature face seals for such valves in aerospace applications with the objective of replacing the existing material, chromium. There's also the sunspot butterfly diagram that demonstrates the periodicity of sunspots.

The most famous allusion to butterflies in science is the butterfly effect, the idea that nonlinear systems can be quite sensitive to initial conditions. A small change has the possibility of producing a large change at a later time. mathematical meteorologist, Edward Lorenz, who discovered this effect in weather simulations, described it in terms of a butterfly's flapping its wings causing a hurricane weeks later. Break out the bug spray!

 Pretty as a picture. German nomenclature for the features of the backside of a butterfly wing (Terminologie der Regionen von Schmetterlingsflügeln). (Illustration by Harald Süpfle, via Wikimedia Commons).

The butterfly best known to electrical engineers is the one embedded in the Cooley–Tukey algorithm, for the fast Fourier transform (FFT). The algorithm includes a butterfly diagram that specifies the data flow of how to combine the results of smaller transforms into a larger transform.[2]

When Cooley and Tukey published their algorithm, they didn't know that Gauss has done a similar mathematical trick in 1805. They can't be faulted, since Gauss had his finger in many mathematical pots during his lifetime, and journal articles more than a hundred years old are hard to find in libraries.

The FFT is a computer version of a transform developed by Joseph Fourier in 1811 to describe heat flow.[3] Today, its most general use is the transformation of signals from the time domain to the frequency domain, and vice-versa. Its applications are numerous, two examples being as a method to filter continuous noise from data streams and a means of data compression. The free and open source (FOSS) application, Audacity, uses FFT techniques to generate frequency histograms, and to filter noise from audio signals.

Since our data streams are becoming faster, it's important for the FFT to live up to the "fast" part of its name. Now, a team of computer scientists from MIT have developed an algorithm for computation of the Fourier transform that's faster than the FFT. The algorithm is not generally applicable, like the FFT. It's restricted to some types of signals; but when it can be applied, the speedup is an order of magnitude. Fortunately, one area to which it can be applied is image compression.[4-5]

MIT professors Dina Katabi and Piotr Indyk, along with Ph.D. candidates Haitham Hassanieh and Eric Price, were scheduled to present their work at the 2012 ACM-SIAM Symposium on Discrete Algorithms (SODA12), January 17-19, Kyoto, Japan. The MIT computer scientists are members of the MIT Sparse Fast Fourier Transform Group.[4]

The algorithm works for sparse signals; namely, those signals in which a few frequencies dominate. The algorithm's speed scales with sparseness, so very sparse signals can be transformed at high speed. Natural signals, such as music, are generally sparse. The algorithm divides the signal into narrow spectral slices such that a given slice will have just one of these dominant frequencies. These spectral filters must be sharp enough to allow selectivity, but they must overlap to include all frequencies.[4]

 Music, especially that made by solo instruments, is a sparse signal.Musica, from The Seven Liberal Arts, by Hans Sebald Beham (1500-1550)(Scan by Nick Michael, via Wikimedia Commons).

The precise location of the dominant frequency in each slice is accomplished by slicing them into smaller regions and discarding those regions below a threshold power level.[4] In a recent arXiv preprint, the authors disclose a more efficient method that samples the signal in the spectral slices at different times to determine the derivative, which indicates whether the frequency is at the high or low end of the slice.[5]

This algorithm computes with order O(k log N), compared with O(N log N) for the conventional FFT, and O(N2) for the regular transform, where k is the number of non-zero Fourier coefficients and N is the number of data points.

References:

Linked Keywords: Butterfly; science; technology; insect; order; Lepidoptera; Coleoptera; Jerry Lewis; Three on a Couch; nerd; engineer; experimentalist; butterfly valve; temperature; face seal; aerospace; chromium; sunspot butterfly diagram; sunspot; allusion; butterfly effect; nonlinear systems; mathematical; meteorologist; Edward Lorenz; weather simulation; hurricane; German; nomenclature; Harald Süpfle; Wikimedia Commons; electrical engineer; Cooley–Tukey algorithm; fast Fourier transform; butterfly diagram; data flow; James Cooley; John Tukey; Carl Friedrich Gauss; transform; Joseph Fourier; heat; signal; time domain; frequency domain; filter; noise; data compression; free and open source; FOSS; Audacity; histogram; computer scientist; Massachusetts Institute of Technology; MIT; algorithm; image compression; Dina Katabi; Piotr Indyk; Haitham Hassanieh; Eric Price; ACM-SIAM Symposium on Discrete Algorithms; Kyoto, Japan; Sparse Fast Fourier Transform Group; frequency; natural; music; solo instrument; Nick Michael; arXiv; derivative; Three on a Couch (1966, Jerry Lewis, Director).

Latest Books by Dev Gualtieri

Thanks to Cory Doctorow of BoingBoing for his favorable review of Secret Codes!

Other Books