  We study the problem of interpolating a noisy Fourier-sparse signal in the
time duration $[0, T]$ from noisy samples in the same range, where the ground
truth signal can be any $k$-Fourier-sparse signal with band-limit $[-F, F]$.
Our main result is an efficient Fourier Interpolation algorithm that improves
the previous best algorithm by [Chen, Kane, Price, and Song, FOCS 2016] in the
following three aspects:
  $\bullet$ The sample complexity is improved from $\widetilde{O}(k^{51})$ to
$\widetilde{O}(k^{4})$.
  $\bullet$ The time complexity is improved from $
\widetilde{O}(k^{10\omega+40})$ to $\widetilde{O}(k^{4 \omega})$.
  $\bullet$ The output sparsity is improved from $\widetilde{O}(k^{10})$ to
$\widetilde{O}(k^{4})$.
  Here, $\omega$ denotes the exponent of fast matrix multiplication. The
state-of-the-art sample complexity of this problem is $\sim k^4$, but was only
known to be achieved by an *exponential-time* algorithm. Our algorithm uses the
same number of samples but has a polynomial runtime, laying the groundwork for
an efficient Fourier Interpolation algorithm.
  The centerpiece of our algorithm is a new sufficient condition for the
frequency estimation task -- a high signal-to-noise (SNR) band condition --
which allows for efficient and accurate signal reconstruction. Based on this
condition together with a new structural decomposition of Fourier signals
(Signal Equivalent Method), we design a cheap algorithm for estimating each
"significant" frequency within a narrow range, which is then combined with a
signal estimation algorithm into a new Fourier Interpolation framework to
reconstruct the ground-truth signal.
