Deterministic sparse fft recovers exact frequencies with certifiable checks
Certificate-Governed CRT Sparse FFT: Verified Global-Label Candidate Construction under Explicit Decoding Models
Data Structures and Algorithms
Summary
Finding the important parts in a huge signal usually takes a lot of time. This paper shows a way to quickly find all the main frequencies in a perfect, sparse signal using a clever math trick. The method guarantees that it either finds exactly the right frequencies or clearly knows when it cannot, by checking the results carefully. The authors also explain how the approach keeps computation efficient even for very big signals.
What this means in practice
- •For signal processing engineers: Recover exact sparse frequency components from high-dimensional noiseless signals efficiently with guaranteed verification.
- •For communications system designers: Design frequency recovery modules that verify sparse signals exactly to improve data decoding reliability in noiseless discrete settings.
Authors
Aaron R. Flouro, Shawn P. Chadwick
Abstract
We present a deterministic CRT-based sparse Fourier architecture for exact recovery of noiseless, on-grid, at-most-\(k\)-sparse spectra with an engineered transform length. The transform length \(N\) is selected as an exact product of small pairwise-coprime stage primes, allowing each stage to use transforms whose size scales with the sparsity rather than the ambient dimension. Three co-prime-increment time shifts provide a one-sided singleton-consistency screen: every genuine singleton passes, while passing collision bins remain provisional candidates. Each candidate bin is mapped by a total label-emission rule to at most one global frequency label, and per-stage label sets are intersected, yielding a deterministic \(O(k)\) candidate bound for every input. Candidate construction uses \(O(k\log N)\) samples. In a comparison real-RAM model with exact arithmetic and exact phase evaluation but without unit-cost root-index decoding, it requires \(O(k\log^2 N/\log k)\) arithmetic operations; in a stronger root-index-oracle model the arithmetic cost is \(O(k\log N)\). Under all-stage genuine-singleton survival, the candidate set contains the true support. Exactness, however, does not depend on that survival condition: a consecutive-sample residual verifier accepts a sparse reconstruction only when it is exact, and all failures route to a dense FFT. The resulting hybrid algorithm therefore returns the exact spectrum for every input in the stated noiseless, on-grid, at-most-\(k\)-sparse model, with \(O(N\log N)\) worst-case runtime. The verified sparse path additionally incurs an \(O(k^2)\) verifier cost in the root-index-oracle model. Neither computational model is a bit-complexity model.