4
$\begingroup$

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

  • 0
    [Quantum](http://area51.stackexchange.com/proposals/36039/quantum-information-and-foundations?referrer=G-oXDJgd8JaWXYyF_kRbzQ2) Fourier Transform: $O(\log^2 N)$2012-11-20
  • 0
    Fastest currently *implemented* algorithm is fftw: fastest Fourier transform in the west. It's $O(n\log n)$ though.2012-11-20
  • 0
    Mmm, ok, additional requirement: one that could be ran on computers we have today. :)2012-11-20
  • 0
    [This](http://arxiv.org/abs/1201.2501v1) seems in the right direction.2012-11-20
  • 0
    You've seen [the Wikipedia page](https://en.wikipedia.org/wiki/Fast_Fourier_transform)? "All known FFT algorithms require $\Theta(N \log N)$ operations... although there is no known proof that a lower complexity score is impossible." It would be interesting if we find out that Wikipedia is out of date, of course.2012-11-20
  • 0
    @just :-( ${ }$2012-11-20
  • 0
    Sorry draks! I actually hope I had a quantum computer..2012-11-20
  • 0
    Join the proposal: They raffle one there, when it goes beta :-)2012-11-20

1 Answers 1

1

There is an algorithm called sparse fast Fourier transform (sFFT), which is faster than FFT algorithms when the Fourier coefficients are sparse.

  • 0
    This appears to be partly the same that was pointed out by WimC (the paper he mentions could be found from the page you provided). I will accept your answer. Thanks also for WimC!2012-11-20