Sirwickentertainment

The Fourier transform, which splits a complicated signal into individual pure frequencies, was devised over 200 years ago but only became widely used after the development of an algorithm called the fast Fourier transform in the 1960s. Now, computer scientist Dina Katabi, Piotr Indyk and their colleagues at the Massachusetts Institute of Technology have developed a Fourier transform algorithm that is potentially hundreds of times faster still.
Splitting a signal using the Fourier transform reveals how much different frequency components contribute to an overall sound or image. In some cases, a wide range of frequencies contribute equally, but often a small number dominate. The MIT algorithm improves performance on signals of the latter type, known as sparse signals.
“Many natural signals have a sparse nature,” says Katabi, including images and sounds. By contrast, human transmissions such as Wi-Fi signals tend to be non-sparse because they are designed to carry as much information as possible by making full use of available frequencies.
The team discovered they could quickly identify the important frequencies in a sparse signal by combining two existing signal filters to create a new, more efficient one. This filter works by dividing the range of frequencies into sets, then identifying which sets contain important frequencies.
Having found the key sets, the team had to identify the exact important frequency within each set. This is usually done by subdividing the set repeatedly until only the important signal remains.