January 18, 2012

A 10x Better Fast Fourier Transform Algorithm from MIT

A 10x better Fast Fourier Transform from MIT. A better FFT algorithm for sparse signals.

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

Tags: better fft algorithm, fft for sparse signals, mit fft algorithm, dina katabi fft algorithm, faster fourier transform algorithm, better fast fourier transform, 10x better FFT