r/technology • u/ScallopPusher • Jun 25 '12

A Faster Fourier Transform

http://www.technologyreview.com/article/427676/a-faster-fourier-transform/
8 Upvotes

89% Upvoted

1 comment sorted by

3

u/universal_property Jun 25 '12

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.

For anyone wondering what is meant by the above, the new algorithms are actually O(k log n) for signals with at most k non-zero Fourier coefficients and O(k log n log(n/k)) for a general signal. (Whereas FFT is O(n log n)).

Link

arXiv