Publication
We 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.