A Deterministic Sub-linear Time Sparse Fourier Algorithm via Non-adaptive Compressed Sensing Methods

Abstract

We study the problem of estimating the best B term Fourier representation for a given frequency-sparse signal (i.e., vector) $\text{A}$ of length $N\gg B$. More explicitly, we investigate how to deterministically identify B of the largest magnitude frequencies of $\hat{\text{A}}$, and estimate their coefficients, in polynomial$(B,\log N)$ time. Randomized sub-linear time algorithms which have a small (controllable) probability of failure for each processed signal exist for solving this problem. However, for failure intolerant applications such as those involving mission-critical hardware designed to process many signals over a long lifetime, deterministic algorithms with no probability of failure are highly desirable. In this paper we build on the deterministic Compressed Sensing results of Cormode and Muthukrishnan (CM) \cite{CMDetCS3,CMDetCS1,CMDetCS2} in order to develop the first known deterministic sub-linear time sparse Fourier Transform algorithm suitable for failure intolerant applications. Furthermore, in the process of developing our new Fourier algorithm, we present a simplified deterministic Compressed Sensing algorithm which improves on CM's algebraic compressibility results while simultaneously maintaining their results concerning exponential decay.

16 pages total, 10 in paper, 6 in appended

Cited by in corpus (7)

• Topics in Compressed Sensing
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Adaptive sub-linear Fourier algorithms
• A New Class of Fully Discrete Sparse Fourier Transforms: Faster Stable Implementations with Guarantees
• Fast DFT Computation for Signals with Structured Support
• (Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless
• Simulating Special but Natural Quantum Circuits