Safety-Certified CRT Sparse FFT: $Ω(k^2)$ Lower Bound and $O(N \log N)$ Worst-Case
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917424771629056 |
|---|---|
| author | Flouro, Aaron R. Chadwick, Shawn P. |
| author_facet | Flouro, Aaron R. Chadwick, Shawn P. |
| contents | Computing Fourier transforms of k-sparse signals, where only k of N frequencies are non-zero, is fundamental in compressed sensing, radar, and medical imaging. While the Fast Fourier Transform (FFT) evaluates all N frequencies in $O(N \log N)$ time, sufficiently sparse signals should admit sub-linear complexity in N. Existing sparse FFT algorithms using Chinese Remainder Theorem (CRT) reconstruction rely on moduli selection choices whose worst-case implications have not been fully characterized.
This paper makes two contributions. First, we establish an $Ω(k^2)$ adversarial lower bound on candidate growth for CRT-based sparse FFT when moduli are not pairwise coprime (specifically when $m_3 \mid m_1 m_2$), implying an $O(k^2 N)$ worst-case validation cost that can exceed dense FFT time. This vulnerability is practically relevant, since moduli must often divide N to avoid spectral leakage, in which case non-pairwise-coprime configurations can be unavoidable. Pairwise coprime moduli avoid the proven attack; whether analogous constructions exist for such moduli remains an open question.
Second, we present a robustness framework that wraps a 3-view CRT sparse front end with lightweight certificates (bucket occupancy, candidate count) and an adaptive dense FFT fallback. For signals passing the certificates, the sparse path achieves $O(\sqrt{N} \log N + k N)$ complexity; when certificates detect collision risk, the algorithm reverts to $O(N \log N)$ dense FFT, guaranteeing worst-case performance matching the classical bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_18911 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Safety-Certified CRT Sparse FFT: $Ω(k^2)$ Lower Bound and $O(N \log N)$ Worst-Case Flouro, Aaron R. Chadwick, Shawn P. Signal Processing Data Structures and Algorithms Information Theory 65T50, 68Q25 F.2.1; G.1.2 Computing Fourier transforms of k-sparse signals, where only k of N frequencies are non-zero, is fundamental in compressed sensing, radar, and medical imaging. While the Fast Fourier Transform (FFT) evaluates all N frequencies in $O(N \log N)$ time, sufficiently sparse signals should admit sub-linear complexity in N. Existing sparse FFT algorithms using Chinese Remainder Theorem (CRT) reconstruction rely on moduli selection choices whose worst-case implications have not been fully characterized. This paper makes two contributions. First, we establish an $Ω(k^2)$ adversarial lower bound on candidate growth for CRT-based sparse FFT when moduli are not pairwise coprime (specifically when $m_3 \mid m_1 m_2$), implying an $O(k^2 N)$ worst-case validation cost that can exceed dense FFT time. This vulnerability is practically relevant, since moduli must often divide N to avoid spectral leakage, in which case non-pairwise-coprime configurations can be unavoidable. Pairwise coprime moduli avoid the proven attack; whether analogous constructions exist for such moduli remains an open question. Second, we present a robustness framework that wraps a 3-view CRT sparse front end with lightweight certificates (bucket occupancy, candidate count) and an adaptive dense FFT fallback. For signals passing the certificates, the sparse path achieves $O(\sqrt{N} \log N + k N)$ complexity; when certificates detect collision risk, the algorithm reverts to $O(N \log N)$ dense FFT, guaranteeing worst-case performance matching the classical bound. |
| title | Safety-Certified CRT Sparse FFT: $Ω(k^2)$ Lower Bound and $O(N \log N)$ Worst-Case |
| topic | Signal Processing Data Structures and Algorithms Information Theory 65T50, 68Q25 F.2.1; G.1.2 |
| url | https://arxiv.org/abs/2604.18911 |