## 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.

Published in:
Algorithmica, 73, 2, 261-288
Year:
2015
Publisher:
New York, Springer Verlag
ISSN:
0178-4617
Keywords:
Laboratories: