Is it possible to make an algorithm faster than the fast Fourier transform to calculate the discrete Fourier transform (is there proofs for or against it)?
OR, a one that only approximates the discrete Fourier transform, but is faster than $O(NlogN)$ and still gives about reasonable results?
Additional requirements:
1) Let's leave the quantum computing out
2) I don't mean faster in sense of how its implemented for some specific hardware, but in the "Big-O notation sense", that it would ran e.g. in linear time.
Sorry for my english