arXiv preprint ·
Certificate-Governed CRT Sparse FFT: Verified Global-Label Candidate Construction under Explicit Decoding Models
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Signal Processing
Best Practices in EEG Analysis: Preprocessing, Modeling, and Machine Learning
Nonnegative DAG Learning via Concomitant Estimation
MyoCodec: A Streaming Neural Codec for Electromyography
Hierarchical Clustering and Signal Denoising on Digraphs
LLM-Based Multi-Agent Systems over Wireless Networks: A Joint Agent--Network Design Perspective
Get the few papers worth your time in Signal Processing every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.