# Improved Algorithms for Learning Fourier-sparse Signals

Preprint · Dongrun Cai, Xue Chen, Xiaowei Shao, Yile Wang

- Archive id: arxiv:2608.06385
- Published: 2026-07-15
- arXiv: https://arxiv.org/abs/2608.06385
- Source URL: https://arxiv.org/abs/2608.06385
- PDF: https://arxiv.org/pdf/2608.06385
- Provenance: arxiv

## Abstract

A classical problem in sparse Fourier transforms, which dates back to the work by Prony in 1795 at least, is to learn a $k$-Fourier-sparse signal $x(t):=\\sum\_{j=1}^k α\_j e^{2 π\\mathbf{i} f\_j t}$ with arbitrary frequencies $f\_1,\\ldots,f\_k$. We study this problem of learning $x(t)$ in a fixed time window $\[-T,T\]$ under adversarial noise with bounded $\\ell\_2$ norm, where the frequencies $f\_1,\\ldots,f\_k$ may be "off-grid" -- arbitrarily located in a given bandlimit $\[-F,F\]$. In particular, our goal is to output a sparse interpolation $\\tilde{x}$ such that $\\tilde{x}(t) \\approx x(t)$ in the time window $\[-T,T\]$. 1. Our first result shows that the sample complexity of interpolation is $k^2 \\cdot O(\\log \\frac{k FT}ε)^2$. While its running time is $(\\frac{k FT}ε)^{O(k)}$, this improves the previous upper bound $k^{4} \\cdot (\\log FT)^{O(1)}$ on the sample complexity substantially and leaves a gap of about $k$ to the lower bound $Ω(k \\log FT)$. 2. Our second result provides efficient algorithms to interpolate $x(t)$. The first algorithm takes $m=k^{3.75} \\cdot (\\log FT)^{O(1)}$ samples and $m^{ω+o(1)}$ time ($ω$ is the matrix multiplication exponent). Assuming that the growth of any $k$-Fourier-sparse signal cannot be significantly larger than the growth of the degree-$(k-1)$ Chebyshev polynomial -- specifically, $x(t) \\le e^{k \\cdot O\\big( \\sqrt{\\frac{\|t\|}{T}-1} \\big)} \\cdot \\underset{s \\in \[-1,1\]}{\\max} \|x(s)\|$ for any $t \\notin \[-T,T\]$, the second algorithm further improves the sample complexity to $m'=k^{3} \\cdot (\\log FT)^{O(1)}$ and the time complexity to $(m')^{ω+o(1)}$.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.