  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.
