  Given an $n$-length input signal $\mbf{x}$, it is well known that its
Discrete Fourier Transform (DFT), $\mbf{X}$, can be computed in $O(n \log n)$
complexity using a Fast Fourier Transform (FFT). If the spectrum $\mbf{X}$ is
exactly $k$-sparse (where $k<<n$), can we do better? We show that
asymptotically in $k$ and $n$, when $k$ is sub-linear in $n$ (precisely, $k
\propto n^{\delta}$ where $0 < \delta <1$), and the support of the non-zero DFT
coefficients is uniformly random, we can exploit this sparsity in two
fundamental ways (i) {\bf {sample complexity}}: we need only $M=rk$
deterministically chosen samples of the input signal $\mbf{x}$ (where $r < 4$
when $0 < \delta < 0.99$); and (ii) {\bf {computational complexity}}: we can
reliably compute the DFT $\mbf{X}$ using $O(k \log k)$ operations, where the
constants in the big Oh are small and are related to the constants involved in
computing a small number of DFTs of length approximately equal to the sparsity
parameter $k$. Our algorithm succeeds with high probability, with the
probability of failure vanishing to zero asymptotically in the number of
samples acquired, $M$.
