{"ID":6536535,"CreatedAt":"2026-07-14T01:21:01.169441415Z","UpdatedAt":"2026-07-14T22:36:59.847166484Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.10501","arxiv_id":"2607.10501","title":"Optimal Extrapolation Bounds for Sparse Fourier Sums","abstract":"We prove an optimal extrapolation theorem for $k$-sparse Fourier sums over arbitrary real frequencies, without any separation assumption, bounding how large such a sum can be just outside an interval on which its energy is observed. For every $g(t)=\\sum_{j=1}^k v_j e^{iλ_jt}$ with $λ_j\\in\\mathbb R$ and every $x\\ge1$, $$ |g(x)|\\le k^{O(1)}\\exp(O(k\\mathop{\\mathrm{arcosh}} x))\\|g\\|_{L^2[-1,1]} . $$ In the endpoint regime, this refines to the explicit bound $$ |g(1+δ)|\\le O(k)\\exp(O(k\\sqrtδ))\\|g\\|_{L^2[-1,1]}, \\qquad 0\\leδ\\le1 . $$ This improves on the $\\exp(O(k^2\\log k\\cdotδ))$ growth estimate of Chen and Price (ICALP 2019), and the exponential scaling is optimal up to constants and polynomial factors in $k$. As an algorithmic consequence, we improve the cluster-center resolution of Chen--Price's clustered-frequency recovery algorithm by a factor of $k$, while preserving its sample complexity up to logarithmic factors. We also obtain exterior leverage-score and transfer bounds for sparse Fourier feature spaces, converting in-domain active-regression guarantees into essentially sharp prediction guarantees just outside the sampling interval.","short_abstract":"We prove an optimal extrapolation theorem for $k$-sparse Fourier sums over arbitrary real frequencies, without any separation assumption, bounding how large such a sum can be just outside an interval on which its energy is observed. For every $g(t)=\\sum_{j=1}^k v_j e^{iλ_jt}$ with $λ_j\\in\\mathbb R$ and every $x\\ge1$, $...","url_abs":"https://arxiv.org/abs/2607.10501","url_pdf":"https://arxiv.org/pdf/2607.10501v1","authors":"[\"Ruizhe Zhang\"]","published":"2026-07-11T22:51:38Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.CA\",\"math.NA\"]","methods":"[]","has_code":false}