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 $$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 )$$f(t)=?j=1kajei?jt+??(?)ei?tdμ(?); i.e., exponential polynomials with a noise term. The frequencies $$\{\omega _j\}$${?j} satisfy $$\omega _j\in [\eta ,2\pi -\eta ]$$?j?[?,2?-?] and $$\min _{i\ne j} |\omega _i-\omega _j|\ge \eta $$mini?j|?i-?j|?? for some $$\eta > 0$$?>0. We design a sublinear time randomized algorithm which, for any $$\epsilon \in (0,\eta /k]$$∈?(0,?/k], which takes $$O(k\log k\log (1/\epsilon )(\log k+\log (\Vert a\Vert _1/\Vert \nu \Vert _1))$$O(klogklog(1/∈)(logk+log(?a?1/???1)) samples of $$f(t)$$f(t) and runs in time proportional to number of samples, recovering $$\omega _j'\approx \omega _j$$?j???j and $$a_j'\approx a_j$$aj??aj such that, with probability $$\varOmega (1)$$Ω(1), the approximation error satisfies $$|\omega _j'-\omega _j|\le \epsilon $$|?j?-?j|≤∈ and $$|a_j-a_j'|\le \Vert \nu \Vert _1/k$$|aj-aj?|≤???1/k for all $$j$$j with $$|a_j|\ge \Vert \nu \Vert _1/k$$|aj|????1/k. We apply our model and algorithm to bearing estimation or source localization and discuss their implications for receiver array processing.