- Medicine - Aug 3 UChicago Medicine supports new organ transplant fund for the uninsured
- Philosophy - Aug 3 Comment: It’s important to understand why some people support capital punishment
- Mathematics - Aug 3 Prize- winning paper yields good vibrations
- Physics - Aug 3 Lab experiment mimics early- stage planetary formation process
- Physics - Aug 3 Notes from the Particle Physics Underground
- Microtechnics - Aug 3 Graphene drives potential for the next- generation of fuel- efficient cars
- Microtechnics - Aug 3 Small tilt in magnets makes them viable memory chips
- Life Sciences - Aug 3 Our elegant brain: motor learning in the fast lane
- Law - Aug 3 New U.S. policies can discourage trophy hunting, Stanford expert says
- Mathematics - Aug 3 New virtual reality headset
- Civil Engineering - Aug 3 Book examines early reformers 'hysteria' over vice in Philadelphia
- Business - Aug 3 Multi- platform media and the digital challenge - an analysis
- Administration - Aug 3 Rising Junior From Penn Returns to Summer Camp, This Time as a Leader
- Life Sciences - Aug 3 The elegant brain: how practice makes perfect
- Medicine - Aug 3 Childhood cancer cells drain immune system’s batteries

# The faster-than-fast Fourier transform

18 January 2012

** 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. **

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.

At the Association for Computing Machinery’s 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.

**Written by:**Larry Hardesty

» Comment on this page.

**Last job offers**

- Medicine/Pharmacology - 3.8

Professeur-e et Médecin-chef-fe du Service de chirurgie cardiovasculaire - Medicine/Pharmacology - 31.7

Senior Lecturer and Researcher - Medicine/Pharmacology - 31.7

Deputy Head of Research - Business/Economics - 31.7

Assistant Professor in Statistics and Econometrics (Big Data) - Pedagogy/Education Science - 30.7

Wissensch. Mitarbeiter/in (70 %) Berufspraktische Studien - Pedagogy/Education Science - 30.7

Wissensch. Mitarbeiter/in (Dissertation, 60 %) Energietechnik und nachhaltige Bildung - Mechanical Engineering - 3.8

Asst. or Assoc. Professor of Air Transport Safety - Medicine/Pharmacology - 3.8

Associate Professorship in Cardiac Genetics - Arts and Design - 15.7

Universitätsprofessorin / Universitätsprofessor für das Fach Musiktheater-Regie (BV gem. § 99 UG ) - Social Sciences - 13.7

Universitätsprofessorin / Universitätsprofessor für das Fach Instrumental- und Gesangspädagogik (BV gem.... - Business/Economics - 3.8

Juniorprofessur W1 (ohne tenure track) für empirische Personalökonomik - Physics/Materials Science - 3.8

/W3-Professur für Physik und ihre Didaktik - Physics/Materials Science - 3.8

Professor / Reader in Novel Methods of Particle Acceleration - Life Sciences - 3.8

Professorship of Immunology - Business/Economics - 2.8

Assistant, Associate, or Full Professor of Management - Medicine/Pharmacology - 1.8

Assistant / Associate Professor - Division of Cardiology