What’s the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid

Abstract

We design a sublinear Fourier sampling algorithm for a case of sparse off-grid frequency recovery. These are signals with the form $f(t) = \sum _{j=1}^k a_j \mathrm{e}^{i\omega _j t} + \int \nu (\omega )\mathrm{e}^{i\omega t}d\mu (\omega )$; i.e., exponential polynomials with a noise term. The frequencies $\{\omega _j\}$ satisfy $\omega _j\in [\eta ,2\pi -\eta ]$ and $\min _{i\ne j} |\omega _i-\omega _j|\ge \eta$ for some $\eta > 0$. We design a sublinear time randomized algorithm which, for any $\epsilon \in (0,\eta /k]$, which takes $O(k\log k\log (1/\epsilon )(\log k+\log (\Vert a\Vert _1/\Vert \nu \Vert _1))$ samples of $f(t)$ and runs in time proportional to number of samples, recovering $\omega _j'\approx \omega _j$ and $a_j'\approx a_j$ such that, with probability $\varOmega (1)$, the approximation error satisfies $|\omega _j'-\omega _j|\le \epsilon$ and $|a_j-a_j'|\le \Vert \nu \Vert _1/k$ for all $j$ with $|a_j|\ge \Vert \nu \Vert _1/k$. We apply our model and algorithm to bearing estimation or source localization and discuss their implications for receiver array processing.