Computing a k-sparse n-length Discrete Fourier Transform using at most 4k samples and O(k log k) complexity
This addresses a fundamental problem in signal processing for applications with sparse spectra, offering significant efficiency gains, though it is incremental as it builds on sparsity exploitation in DFT computation.
The paper tackles the problem of computing a k-sparse Discrete Fourier Transform (DFT) more efficiently than the standard O(n log n) FFT by exploiting sparsity, achieving results of using at most 4k samples and O(k log k) computational complexity with high probability for sub-linear k.
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^δ$ where $0 < δ<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 < δ< 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$.