| Tikalon Blog is now in archive mode.
An easily printed and saved version of this article, and a link
to a directory of all articles, can be found below: |
|
This article |
| Directory of all articles |
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(N
2) for the regular transform, where k is the number of non-zero Fourier coefficients and N is the number of data points.
References:
- Three on a Couch (1966, Jerry Lewis, Director) on the Internet Movie Database.
- James W. Cooley and John W. Tukey, "An algorithm for the machine calculation of complex Fourier series," Math. Comp., vol. 19 (1965), pp. 297-301. A PDF file is available, here.
- Larry Hardesty, "Explained: The Discrete Fourier Transform," MIT Press Release, November 25, 2009.
- Larry Hardesty, "The faster-than-fast Fourier transform," MIT Press Release, January 18, 2012.
- Haitham Hassanieh, Piotr Indyk, Dina Katabi and Eric Price, "Nearly Optimal Sparse Fourier Transform," arXiv Preprint Server, January 12, 2012.
Permanent Link to this article
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).