Authors: Petros Boufounos Volkan Cevher Anna C Gilbert Yi Li Martin J Strauss
Publish Date: 2014/07/22
Volume: 73, Issue: 2, Pages: 261-288
Abstract
We design a sublinear Fourier sampling algorithm for a case of sparse offgrid frequency recovery These are signals with the form ft = sum j=1k a j mathrmeiomega j t + int nu omega mathrmeiomega tdmu omega ie exponential polynomials with a noise term The frequencies omega j satisfy omega jin eta 2pi eta and min ine j omega iomega jge eta for some eta 0 We design a sublinear time randomized algorithm which for any epsilon in 0eta /k which takes Oklog klog 1/epsilon log k+log Vert aVert 1/Vert nu Vert 1 samples of ft and runs in time proportional to number of samples recovering omega japprox omega j and a japprox a j such that with probability varOmega 1 the approximation error satisfies omega jomega jle epsilon and a ja jle Vert nu Vert 1/k for all j with a jge Vert nu Vert 1/k We apply our model and algorithm to bearing estimation or source localization and discuss their implications for receiver array processingThe authors would like to thank an anonymous reviewer of APPROX/RANDOM 2012 for the suggestion of improving the running time V Cevher was partially supported by Faculty Fellowship at Rice University MIRG268398 ERC Future Proof and DARPA KeCoM program 11DARPA1055 A C Gilbert was partially supported by NSF DMS 0743372 and DARPA ONR N660010612011 Y Li was partially supported by NSF DMS 0743372 when the author was at University of Michigan Ann Arbor M J Strauss was partially supported by NSF DMS 0743372 and DARPA ONR N660010612011
Keywords: