The Fourier transform is a method for representing an irregular signal as a combination of weighted sine waves or ‘frequencies’. To calculate it quickly the Fast Fourier Transform (FFT) was devised some 50 years ago and ever since people have been searching for methods to make it even faster. At MIT a group of researchers has now developed an algorithm that, in a large range of practically important cases, achieves an up to a tenfold speed increase.

 

Signals whose Fourier transforms contain a relatively small number of strong frequencies are called ‘sparse’. In nature, most of the normal signals are sparse. The new algorithm determines the weights of the strongest frequency components contained in a signal; 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.

 

The new algorithm relies on two key ideas. The first is to divide a signal into narrow slices of bandwidth, sized so that a slice will generally contain only one strong frequency component. The second is an efficient strategy, borrowed from 4G cellular networks, to identify the strongest frequency in each slice by sampling it at different times.

 

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.