Title:  Nearly Optimal Sparse Fourier Transform

Abstract:

We consider the problem of computing the k-sparse approximation to the
discrete Fourier transform of an n-dimensional signal. We show:

- An O(k log n)-time randomized algorithm for the case where the input
  signal has at most k non-zero Fourier coefficients, and

- An O(k log n log(n/k))-time randomized algorithm for general input
  signals.

Both algorithms achieve o(n log n) time, and thus improve over the
Fast Fourier Transform, for any k = o(n). They are the first known
algorithms that satisfy this property. Also, if one assumes that the
Fast Fourier Transform is optimal, the algorithm for the exactly
k-sparse case is optimal for any k = n^{Omega(1)}.

We complement our algorithmic results by showing that any algorithm
for computing the sparse Fourier transform of a general signal must
use at least Omega(k log(n/k) / log log n) signal samples, even if it
is allowed to perform adaptive sampling.