Boufounos, PetrosCevher, VolkanGilbert, Anna C.Li, YiStrauss, Martin J.2015-01-222015-01-222015-01-22201510.1007/s00453-014-9918-0https://infoscience.epfl.ch/handle/20.500.14299/110476WOS:000360668100002We design a sublinear Fourier sampling algorithm for a case of sparse off-grid frequency recovery. These are signals with the form f(t)=∑kj=1ajeiωjt+ν^ , t∈Z ; i.e., exponential polynomials with a noise term. The frequencies {ω j } satisfy ω j  ∈ [η,2π − η] and min i ≠ j |ω i  − ω j | ≥ η for some η > 0. We design a sublinear time randomized algorithm, which takes O(klogklog(1/η)(logk + log( ∥ a ∥ 1/ ∥ ν ∥ 1)) samples of f(t) and runs in time proportional to number of samples, recovering {ω j } and {a j } such that, with probability Ω(1), the approximation error satisfies |ω j ′ − ω j | ≤ η/k and |a j  − a j ′| ≤ ∥ ν ∥ 1/k for all j with |a j | ≥ ∥ ν ∥ 1/k.text::journal::journal article::research article