5
$\begingroup$

I found out some bounds on the Discrete Fourier Transform calculation on certain models of computation but nothing on attempts at finding algorithms asymptotically faster than the Cooley-Tukey FFT on the RAM model of computation. The Discrete Fourier Transform can be defined as follows: Given a sequence $x_0,x_2..,x_{N-1}$ of $N$ complex numbers transform them into $X_0,..,X_{N-1}$ with: $$X_k = \sum_{n=0}^{N-1} x_n \cdot e^{-i2\pi \tfrac{k}{N}n}$$

Historically are there any documented attempts at finding algorithms that are asymptotically faster than the FFT for the Discrete Fourier Transform?

Improve this question
$\endgroup$
2
  • $\begingroup$ Reversing, the question, why would you expect there to be any? Outside of specific restricted inputs, such as sparse data, O(N log N) looks to be already optimal. We have n input values to turn into n output values, where every output depends on every input in a reversible fashion. Calculating any single of them already takes N operations, so getting the rest for only O(log N) times that already sounds like a bargain to me. Also, as memory is limited, for any practical problem, log N is just a multiplicative constant and the question rather boils down to which is the faster implementation. $\endgroup$
    – mlk
    Commented Jun 27 at 12:46
  • $\begingroup$ @mlk Since there isn't any proof that no linear time algorithm is obtainable and given that the dft has several important applications I would assume that some scientists have tried to obtain a linear algorithm or at least a proof that such algorithm doesn't exist in general RAM setting lets say. $\endgroup$
    – Nicolaus
    Commented Jun 27 at 14:05

1 Answer 1

Reset to default
8
$\begingroup$

A set of sub-linear algorithms for the Discrete/Fast Fourier Transform if the sought spectrum is sparse have been developed. These developments are spread out over about the past three decades. For a review of this line of research see:

Let $s$ be the number of samples and $k$ be the $k$-sparcity of the spectrum, then the runtime is $O(k \log s)$, which for fixed $k < s$ is sub-linear. While sublinear performance is asymptotically better than the FFT's asymptotic runtime of $O(n\log n)$ it is not a straight-up general improvement due to the sparsity requirement.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.