Nearly Optimal Sparse Fourier Transform (abstract)Apparently this new algorithm works in
O(n log n) time for "sparse" data sets, compared to the same result in optimal cases for the
Fast Fourier Transform.
The existence of DFT algorithms faster than FFT is one of the central questions in the theory of algorithms.
A general algorithm for computing the exact DFT must take time at least proportional to its output size, i.e., Ω(n)....For sparse signals, the Ω(n) lower bound for the complexity of DFT no longer applies. If a signal has a small number k of non-zero Fourier coefficients – the exactly k-sparse case – the output of the Fourier transform can be represented succinctly using only k coefficients....The key property of both algorithms is their ability to achieve o(n log n) time, and thus improve over the FFT, for any k = o(n). These algorithms are the first known algorithms that satisfy this property.
