Featured Research

from universities, journals, and other organizations

Leaner Fourier transforms: New algorithm can separate signals into their individual frequencies using a minimal number of samples

Date:
December 11, 2013
Source:
Massachusetts Institute of Technology
Summary:
A new algorithm performs Fourier transforms using a minimal number of samples. The fast Fourier transform, one of the most important algorithms of the 20th century, revolutionized signal processing. The algorithm allowed computers to quickly perform Fourier transforms -- fundamental operations that separate signals into their individual frequencies -- leading to developments in audio and video engineering and digital data compression.

A new algorithm performs Fourier transforms using a minimal number of samples.
Credit: Christine Daniloff/MIT

The fast Fourier transform, one of the most important algorithms of the 20th century, revolutionized signal processing. The algorithm allowed computers to quickly perform Fourier transforms -- fundamental operations that separate signals into their individual frequencies -- leading to developments in audio and video engineering and digital data compression.

But ever since its development in the 1960s, computer scientists have been searching for an algorithm to better it.

Last year MIT researchers Piotr Indyk and Dina Katabi did just that, unveiling an algorithm that in some circumstances can perform Fourier transforms hundreds of times more quickly than the fast Fourier transform (FFT).

Now Indyk, a professor of computer science and engineering and a member of the Theory of Computation Group within the Computer Science and Artificial Intelligence Laboratory (CSAIL), and his team have gone a step further, significantly reducing the number of samples that must be taken from a given signal in order to perform a Fourier transform operation.

Close to theoretical minimum

In a paper to be presented at the ACM-SIAM Symposium on Discrete Algorithms in January, Indyk, postdoc Michael Kapralov, and former student Eric Price will reveal an algorithm that can perform Fourier transforms using close to the theoretical minimum number of samples. They have also bettered even this, developing an algorithm that uses the minimum possible number of signal samples.

This could significantly reduce the time it takes medical devices such as magnetic resonance imaging (MRI) and nuclear magnetic resonance (NMR) machines to scan patients, or allow astronomers to take more detailed images of the universe, Indyk says.

The Fourier transform is a fundamental mathematical notion that allows signals to be broken down into their component parts. When you listen to someone speak, for example, you can hear a dominant tone, which is the principal frequency in their voice. "But there are many other underlying frequencies, which is why the human voice is not a single tone, it's much richer than that," Indyk says. "So in order to understand what the spectrum looks like, we need to decompose the sounds into their basic frequencies, and that is exactly what the Fourier transform does."

The development of the FFT automated this process for the first time, allowing computers to rapidly manipulate and compress digital signals into a more manageable form. This is possible because not all of the frequencies within a digital signal are equal. Indeed, in nature many signals contain just a few dominant frequencies and a number of far less important ones, which can be safely disregarded. These are known as sparse signals.

"In real life, often when you look at a signal, there are only a small number of frequencies that dominate the spectrum," Indyk says. "So we can compress [the signal] by keeping only the top 10 percent of these."

Indyk and Katabi's previous work focused on the length of time their algorithm needed to perform a sparse Fourier transform operation. However, in many applications, the number of samples the algorithm must take of the signal can be as important as its running time.

Applications in medical imaging, astronomy

One such example is in MRI scanning, Indyk says. "The device acquires Fourier samples, basically snapshots of the body lying inside the machine, which it uses to recover the inner structure of the body," he says. "In this situation, the number of samples taken is directly proportionate to the amount of time that the patient has to spend in the machine."

So by allowing the MRI scanner to produce an image of the body using a fraction of the samples needed by existing devices, it could significantly reduce the time patients must spend lying still inside the narrow, noisy machines.

The team is also investigating the idea of using the new sparse Fourier transform algorithm in astronomy. They are working with researchers at the MIT Haystack Observatory, who specialize in radio astronomy, to use the system in interferometry, in which signals from an array of telescopes are combined to produce a single, high-resolution image of space. Applying the sparse Fourier transform algorithm to the telescope signals would reduce the number of observations needed to produce an image of the same quality, Indyk says.

"That's important," he says, "because these are really massive data sets, and to make matters worse, much of this data is distributed because there are several different, separated telescopes, and each of them acquires some of the information, and then it all has to be sent to the same place to be processed."

What's more, radio telescopes are extremely expensive to build, so an algorithm that allows astronomers to use fewer of them, or to obtain better quality images from the same number of sensors, could be extremely important, he says.

Martin Strauss, a professor of mathematics, electrical engineering, and computer science at the University of Michigan, who develops fundamental algorithms for applications such as signal processing and massive data sets, says work by Indyk and others makes sparse Fourier transform algorithms advantageous over the celebrated FFT on a larger class of problems than before. "The current paper squeezes out nearly all [of the performance] that is possible with these methods," he says.


Story Source:

The above story is based on materials provided by Massachusetts Institute of Technology. Note: Materials may be edited for content and length.


Cite This Page:

Massachusetts Institute of Technology. "Leaner Fourier transforms: New algorithm can separate signals into their individual frequencies using a minimal number of samples." ScienceDaily. ScienceDaily, 11 December 2013. <www.sciencedaily.com/releases/2013/12/131211131826.htm>.
Massachusetts Institute of Technology. (2013, December 11). Leaner Fourier transforms: New algorithm can separate signals into their individual frequencies using a minimal number of samples. ScienceDaily. Retrieved July 28, 2014 from www.sciencedaily.com/releases/2013/12/131211131826.htm
Massachusetts Institute of Technology. "Leaner Fourier transforms: New algorithm can separate signals into their individual frequencies using a minimal number of samples." ScienceDaily. www.sciencedaily.com/releases/2013/12/131211131826.htm (accessed July 28, 2014).

Share This




More Matter & Energy News

Monday, July 28, 2014

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

Europe's Highest Train Turns 80 in French Pyrenees

Europe's Highest Train Turns 80 in French Pyrenees

AFP (July 25, 2014) Europe's highest train, the little train of Artouste in the French Pyrenees, celebrates its 80th birthday. Duration: 01:05 Video provided by AFP
Powered by NewsLook.com
TSA Administrator on Politics and Flight Bans

TSA Administrator on Politics and Flight Bans

AP (July 24, 2014) TSA administrator, John Pistole's took part in the Aspen Security Forum 2014, where he answered questions on lifting of the ban on flights into Israel's Tel Aviv airport and whether politics played a role in lifting the ban. (July 24) Video provided by AP
Powered by NewsLook.com
Creative Makeovers for Ugly Cellphone Towers

Creative Makeovers for Ugly Cellphone Towers

AP (July 24, 2014) Mobile phone companies and communities across the country are going to new lengths to disguise those unsightly cellphone towers. From a church bell tower to a flagpole, even a pencil, some towers are trying to make a point. (July 24) Video provided by AP
Powered by NewsLook.com
Algonquin Power Goes Activist on Its Target Gas Natural

Algonquin Power Goes Activist on Its Target Gas Natural

TheStreet (July 23, 2014) When The Deal's Amanda Levin exclusively reported that Gas Natural had been talking to potential suitors, the Ohio company responded with a flat denial, claiming its board had not talked to anyone about a possible sale. Lo and behold, Canadian utility Algonquin Power and Utilities not only had approached the company, but it did it three times. Its last offer was for $13 per share as Gas Natural's was trading at a 60-day moving average of about $12.50 per share. Now Algonquin, which has a 4.9% stake in Gas Natural, has taken its case to shareholders, calling on them to back its proposals or, possibly, a change in the target's board. Video provided by TheStreet
Powered by NewsLook.com

Search ScienceDaily

Number of stories in archives: 140,361

Find with keyword(s):
Enter a keyword or phrase to search ScienceDaily for related topics and research stories.

Save/Print:
Share:

Breaking News:
from the past week

In Other News

... from NewsDaily.com

Science News

Health News

Environment News

Technology News



Save/Print:
Share:

Free Subscriptions


Get the latest science news with ScienceDaily's free email newsletters, updated daily and weekly. Or view hourly updated newsfeeds in your RSS reader:

Get Social & Mobile


Keep up to date with the latest news from ScienceDaily via social networks and mobile apps:

Have Feedback?


Tell us what you think of ScienceDaily -- we welcome both positive and negative comments. Have any problems using the site? Questions?
Mobile: iPhone Android Web
Follow: Facebook Twitter Google+
Subscribe: RSS Feeds Email Newsletters
Latest Headlines Health & Medicine Mind & Brain Space & Time Matter & Energy Computers & Math Plants & Animals Earth & Climate Fossils & Ruins