204727
20181203023732.0
0178-4617
10.1007/s00453-014-9918-0
doi
ARTICLE
What’s the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid
2015
Springer Verlag
2015
Journal Articles
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.
Boufounos, Petros
Cevher, Volkan
199128
243957
Gilbert, Anna C.
Li, Yi
Strauss, Martin J.
261–288
2
Algorithmica -New York-
73
439144
http://infoscience.epfl.ch/record/204727/files/offgrid.pdf
LIONS
252306
U12179
oai:infoscience.tind.io:204727
article
STI
231598
148230
EPFL-ARTICLE-204727
EPFL
PUBLISHED
REVIEWED
ARTICLE