Computing a k-sparse n-length Discrete Fourier Transform using at most 4k samples and O(k log k) complexity

Abstract

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$.

36 pages, 15 figures. To be presented at ISIT-2013, Istanbul Turkey

References in corpus (2)

• A Fast Hadamard Transform for Signals with Sub-linear Sparsity in the Transform Domain
• Sample-Optimal Average-Case Sparse Fourier Transform in Two Dimensions

Cited by in corpus (5)

• Sub-linear Time Support Recovery for Compressed Sensing using Sparse-Graph Codes
• Fast and Efficient Sparse 2D Discrete Fourier Transform using Sparse-Graph Codes
• SPRIGHT: A Fast and Robust Framework for Sparse Walsh-Hadamard Transform
• A sparse multidimensional FFT for real positive vectors
• A Generalized LDPC Framework for Robust and Sublinear Compressive Sensing