Skip to Content

A Faster Fourier Transform

A mathematical upgrade promises a speedier digital world.
Piotr Indyk, Dina Katabi, Eric Price, and Haitham Hassanieh (left to right) have created a faster way to break down complex signals into combinations of simple waves for processing.

In January, four MIT researchers showed off a replacement for one of the most important algorithms in computer science. Dina Katabi, Haitham Hassanieh, Piotr Indyk, and Eric Price have created a faster way to perform the Fourier transform, a mathematical technique for processing streams of data that underlies the operation of things such as digital medical imaging, Wi-Fi routers, and 4G cellular networks.

The principle of the Fourier transform, which dates back to the 19th century, is that any signal, such as a sound recording, can be represented as the sum of a collection of sine and cosine waves with different frequencies and amplitudes. This collection of waves can then be manipulated with relative ease—for example, allowing a recording to be compressed or noise to be suppressed. In the mid-1960s, a computer-friendly algorithm called the fast Fourier transform (FFT) was developed. Anyone who’s marveled at the tiny size of an MP3 file compared with the same recording in an uncompressed form has seen the power of the FFT at work.

With the new algorithm, called the sparse Fourier transform (SFT), streams of data can be processed 10 to 100 times faster than was possible with the FFT. The speedup can occur because the information we care about most has a great deal of structure: music is not random noise. These meaningful signals typically have only a fraction of the possible values that a signal could take; the technical term for this is that the information is “sparse.” Because the SFT algorithm isn’t intended to work with all possible streams of data, it can take certain shortcuts not otherwise available. In theory, an algorithm that can handle only sparse signals is much more limited than the FFT. But “sparsity is everywhere,” points out coinventor Katabi, a professor of electrical engineering and computer science. “It’s in nature; it’s in video signals; it’s in audio signals.”

A faster transform means that less computer power is required to process a given amount of information—a boon to energy-conscious mobile multimedia devices such as smart phones. Or with the same amount of power, engineers can contemplate doing things that the computing demands of the original FFT made impractical. For example, Internet backbones and routers today can actually read or process only a tiny trickle of the river of bits they pass between them. The SFT could allow researchers to study the flow of this traffic in much greater detail as bits shoot by billions of times a second.

Keep Reading

Most Popular

The inside story of how ChatGPT was built from the people who made it

Exclusive conversations that take us behind the scenes of a cultural phenomenon.

How Rust went from a side project to the world’s most-loved programming language

For decades, coders wrote critical systems in C and C++. Now they turn to Rust.

Design thinking was supposed to fix the world. Where did it go wrong?

An approach that promised to democratize design may have done the opposite.

Sam Altman invested $180 million into a company trying to delay death

Can anti-aging breakthroughs add 10 healthy years to the human life span? The CEO of OpenAI is paying to find out.

Stay connected

Illustration by Rose Wong

Get the latest updates from
MIT Technology Review

Discover special offers, top stories, upcoming events, and more.

Thank you for submitting your email!

Explore more newsletters

It looks like something went wrong.

We’re having trouble saving your preferences. Try refreshing this page and updating them one more time. If you continue to get this message, reach out to us at customer-service@technologyreview.com with a list of newsletters you’d like to receive.