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)=∑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.