Optimal Extrapolation Bounds for Sparse Fourier Sums
Abstract
We prove a sharp extrapolation bound for k-sparse Fourier sums with arbitrary real frequencies and no separation assumption. For every g(t)=∑j=1k vjeiλjt with λj∈ℝ and every x≥ 1, |g(x)|≤ kexp(O(karcosh x))|g|L2[−1,1]. Near the endpoint at x=1+δ, this gives an exponential factor of exp(O(k√δ)), improving on the exp(O(k2log k·δ)) estimate of Chen and Price (ICALP 2019), and the exponent is optimal up to a constant factor. Our theorem has algorithmic applications to recovering gapless Fourier-sparse signals: it improves the resolution of cluster-location algorithms and the sample complexity of Fourier interpolation algorithms. In addition, it gives sharp bounds on the error transfer of sparse Fourier models just outside the training interval.
Related
- Near-Optimal Quantum Lower Bounds for Convex Optimization via Fourier Rank
- Independent powers and bounded Fourier partial sums in L1
- Selection, Representation, and Execution in Sparse Fourier Neural Operators
- Minkowski sums with convex curves without pointwise Fourier decay
- Gaussian Lower Bounds for Distinct Subset Sums in Higher Dimensions
BibTeX
@misc{zhang2026optimal,
title = {{Optimal Extrapolation Bounds for Sparse Fourier Sums}},
author = {Ruizhe Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2607.10501},
eprint = {2607.10501},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.10501},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal Extrapolation Bounds for Sparse Fourier Sums
AU - Ruizhe Zhang
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2607.10501
UR - https://arxiv.org/abs/2607.10501
AB - We prove a sharp extrapolation bound for k-sparse Fourier sums with arbitrary real frequencies and no separation assumption. For every g(t)=∑_j=1^k v_je^iλ_jt with λ_j∈ℝ and every x≥ 1, |g(x)|≤ kexp(O(karcosh x))|g|_L^2[−1,1]. Near the endpoint at x=1+δ, this gives an exponential factor of exp(O(k√δ)), improving on the exp(O(k^2log k·δ)) estimate of Chen and Price (ICALP 2019), and the exponent is optimal up to a constant factor. Our theorem has algorithmic applications to recovering gapless Fourier-sparse signals: it improves the resolution of cluster-location algorithms and the sample complexity of Fourier interpolation algorithms. In addition, it gives sharp bounds on the error transfer of sparse Fourier models just outside the training interval.
ER -