With all due respect, this is anything but sensationalism. It might help to understand that the number of FFT coefficients computed is not necessarily the number of data points processed. Theoretically, if we have a perfect cosine, for example, we'd get TWO non-zero coefficients (k=2) even if n was a huge number. Compare O(k logn log(n/k)) to O(nlogn) in those cases!

Granted, this doesn't apply to every single situation. However, citing the article in the case of video signals, you have on average 7 "non-negligible" coefficients (k~7). So there are certainly applications that will benefit dramatically from this.

We disagree.

The big-O results of the paper are interesting and with more work could prove a starting point for improvements in very long FFTs. Why long? Because, for big-O asymptotics to kick in, you'll need large n.

But, the domain of applicability seems to be a niche. The "7 non-negligible coefficients" result you refer to is for 8x8 DCT's (as in JPEG). That's n = 8. There are optimized implementations for the small-n cases that will utterly dominate a big-O optimal algorithm like this. Compare Strassen's algorithm for matrix *.

Have you looked at the code complexity of the algorithm in the paper? There are several interlocking components (hash functions, rebinning) that have their own big-O optimality claims and, in some cases, randomization. Getting it all to work together efficiently, given cache issues, even for large n (say, 10^6) would be a serious engineering challenge. People have been working on optimizing data flow for FFT for decades now, and the state of the art is very advanced.

I agree, that the result is interesting in principle. Runtime is actually sub-linear in n, the sequence length.

Thanks :) left that important bit out. This is opposed to O(n log n) for what's been around.

But it's MIT so anything and everything they do has to be awesome.