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

We design a sublinear Fourier sampling algorithm for a case of sparse off-grid frequency recovery. These are signals with the form ; i.e., exponential polynomials with a noise term. The frequencies satisfy and for some . We design a sublinear time randomized algorithm which, for any , which takes samples of and runs in time proportional to number of samples, recovering and such that, with probability , the approximation error satisfies and for all with . We apply our model and algorithm to bearing estimation or source localization and discuss their implications for receiver array processing.