TY - EJOUR
DO - 10.1007/s00453-014-9918-0
AB - 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.
T1 - What’s the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid
IS - 2
DA - 2015
AU - Boufounos, Petros
AU - Cevher, Volkan
AU - Gilbert, Anna C.
AU - Li, Yi
AU - Strauss, Martin J.
JF - Algorithmica -New York-
SP - 261–288
VL - 73
EP - 261–288
PB - Springer Verlag
ID - 204727
SN - 0178-4617
UR - http://infoscience.epfl.ch/record/204727/files/offgrid.pdf
ER -