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)={\sum }_{j=1}^k{v}_j{e}^{i{\lambda }_{j}t}$ with ${\lambda }_j\in \mathbb{R}$ and every $x\ge 1$, \begin{align*} |g(x)|\le k\exp(O(k\operatorname{arcosh} x))\|g\|_{L^2[-1,1]}. \end{align*} Near the endpoint at $x=1+\delta$, this gives an exponential factor of $\exp (O(k\sqrt{\delta }))$, improving on the $\exp (O(k^2\log k\cdot \delta ))$ 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.