Deterministic Sparse FFT via Keyed Multi-View Gating with $O(\sqrt{N} \log k)$ Expected Time
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909014677258240 |
|---|---|
| author | Flouro, Aaron R. Chadwick, Shawn P. |
| author_facet | Flouro, Aaron R. Chadwick, Shawn P. |
| contents | We introduce a deterministic sparse Fourier transform framework based on a keyed multi-view gating mechanism that leverages 2-of-3 Chinese Remainder Theorem (CRT) agreement to reduce candidate frequency pairs from $O(k^2)$ to $Θ(k)$ under sparse-regime assumptions. Unlike prior approaches that rely on randomized bucketization for candidate formation, the proposed method provides deterministic structure with probabilistic guarantees arising only from assumptions on frequency placement and independence of affine hashing across views. The algorithm is realized through a peeling-based recovery procedure that extracts frequencies directly from singleton bins without explicit pair enumeration. A recursive self-reduction eliminates the $O(\sqrt{N} \log N)$ preprocessing floor, yielding $O(\sqrt{N} \log k)$ expected identification time while maintaining an $O(N \log N)$ worst-case bound via deterministic dense-FFT fallback. A multi-view verification framework combining Parseval energy consistency and bin-wise residual checks ensures bounded failure probability and no false negatives under correct verification. This establishes a framework combining deterministic candidate reduction, sublinear expected complexity, and worst-case safety guarantees within a CRT-based sparse FFT architecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_03935 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Deterministic Sparse FFT via Keyed Multi-View Gating with $O(\sqrt{N} \log k)$ Expected Time Flouro, Aaron R. Chadwick, Shawn P. Signal Processing Data Structures and Algorithms Information Theory 68W40, 94A12 F.2.2; G.4 We introduce a deterministic sparse Fourier transform framework based on a keyed multi-view gating mechanism that leverages 2-of-3 Chinese Remainder Theorem (CRT) agreement to reduce candidate frequency pairs from $O(k^2)$ to $Θ(k)$ under sparse-regime assumptions. Unlike prior approaches that rely on randomized bucketization for candidate formation, the proposed method provides deterministic structure with probabilistic guarantees arising only from assumptions on frequency placement and independence of affine hashing across views. The algorithm is realized through a peeling-based recovery procedure that extracts frequencies directly from singleton bins without explicit pair enumeration. A recursive self-reduction eliminates the $O(\sqrt{N} \log N)$ preprocessing floor, yielding $O(\sqrt{N} \log k)$ expected identification time while maintaining an $O(N \log N)$ worst-case bound via deterministic dense-FFT fallback. A multi-view verification framework combining Parseval energy consistency and bin-wise residual checks ensures bounded failure probability and no false negatives under correct verification. This establishes a framework combining deterministic candidate reduction, sublinear expected complexity, and worst-case safety guarantees within a CRT-based sparse FFT architecture. |
| title | Deterministic Sparse FFT via Keyed Multi-View Gating with $O(\sqrt{N} \log k)$ Expected Time |
| topic | Signal Processing Data Structures and Algorithms Information Theory 68W40, 94A12 F.2.2; G.4 |
| url | https://arxiv.org/abs/2605.03935 |