Improved Algorithms for Learning Fourier-sparse Signals

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{\alpha }_j{e}^{2\pi \mathbf{i}{f}_{j}t}$ with arbitrary frequencies $f_1,\dots ,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,\dots ,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{kFT}{\epsilon }{)}^2$. While its running time is $(\frac{kFT}{\epsilon }{)}^{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 $\Omega (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^{\omega +o(1)}$ time ($\omega$ 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\left(\sqrt{\frac{|t|}{T}-1}\right)}\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^{\prime }=k^3\cdot (\log FT{)}^{O(1)}$ and the time complexity to $(m^{\prime }{)}^{\omega +o(1)}$.