Metraipolis › archive › dc_dc66a257f032
Learning Multiband Signals and Fourier-sparse Signals — arXiv:2609.02977
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.02977
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T03:01:17.108Z
- SHA-256 of the archived text
462670cc465b88314d799da3533806213652c7ef3e20be2e692a48e25eb9ba66- Stable URL of this page
https://metraipolis.com/documento/dc_dc66a257f032
How to cite
Learning Multiband Signals and Fourier-sparse Signals — arXiv:2609.02977 — arXiv (en), https://arxiv.org/abs/2609.02977 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dc66a257f032 (Metraipolis archive dc_dc66a257f032, sha256 462670cc465b88314d799da3533806213652c7ef3e20be2e692a48e25eb9ba66)
BibTeX
@misc{dcdc66a257f032,
title = {Learning Multiband Signals and Fourier-sparse Signals — arXiv:2609.02977},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.02977},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dc66a257f032; sha256 462670cc465b88314d799da3533806213652c7ef3e20be2e692a48e25eb9ba66},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.02977. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We consider efficient algorithms to learn multiband signals and Fourier-sparse signals. A mutliband signal has a Fourier transform supported by a bounded number of intervals, say $I_1 \cup I_2 \cdots \cup I_n$. There is a long line of research on multiband signals. In particular, Avron et al. showed an efficient reconstructing algorithm whose sample complexity is almost optimal. However, all previous algorithms for multiband signals consider the reconstructing problem in which the locations of $I_1,\ldots,I_n$ are given as a priori knowledge. On the other hand, although the problem of learning Fourier-sparse signals with $k$ arbitrary frequencies dates at least to Prony in 1795, designing efficient and robust learning algorithms is still an open problem. The state-of-the-art is an efficient algorithm of $\tilde{O}(k^3)$ samples and $\tilde{O}(k^{3 \omega})$ time from the very recent work by Cai et al., while the statistical upper bound is $\tilde{O}(k^2)$ samples. Let $[-1,1]$ be the time window in which the noise is $\ell_2$ bounded. 1. We show an efficient algorithm to recover the locations of the bands $I_1,\ldots,I_n$ in $\hat{x}$ within $\tilde{O}(n+\sum_i |I_i|)$ samples and $\tilde{O}(n+\sum_i |I_i|)$ time. Furthermore, combining this with the reconstructing algorithm by Avron et al. provides an efficient interpolation algorithm within $\tilde{O}(n+\sum_i |I_i|)$ samples. 2. We show that every $k$-Fourier-sparse signal $x$ admits a multiband approximation $z$ whose Fourier transform is of support size $|\mathrm{supp}(\hat{z})|=\tilde{O}(k^2)$. Furthermore, we show an interpolation algorithm for $k$-Fourier-sparse signals with $\tilde{O}(k^2)$ samples and $\tilde{O}(k^5)$ time.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-04 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.02977 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T02:39:14.116Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-04?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).