Fetching the paper…
Reading the bibliography…
We give an algorithm for $\ell_2/\ell_2$ sparse recovery from Fourier measurements using $O(k\log N)$ samples, matching the lower bound of \cite{DIPW} for non-adaptive algorithms up to constant factors for any $k\leq N^{1-\delta}$.
The Theory of Error-Correcting Codes
F.J. MacWilliams and N.J.A. Sloane · 1978
Earlier work this paper cites.
A hard-corepredicate for allone-way functions
O. Goldreich and L. Levin · 1989
Earlier work this paper cites.
Elements of Information Theory
T. Cover and J. Thomas · 1991
Earlier work this paper cites.
Learning decision trees using the Fourier spectrum
E. Kushilevitz and Y. Mansour · 1991
Earlier work this paper cites.
Randomized interpolation and approximation of sparse polynomials
Y. Mansour · 1992
Earlier work this paper cites.
Finding frequent items in data streams
M. Charikar, K. Chen, and M. Farach-Colton · 2002
Earlier work this paper cites.
Near-optimal sparse Fourier representations via sampling
A. Gilbert, S. Guha, P. Indyk, M. Muthukrishnan, and M. Strauss · 2002
Earlier work this paper cites.
Proving hard-core predicates using list decoding
A. Akavia, S. Goldwasser, and S. Safra · 2003
Earlier work this paper cites.
Fourier Analysis:An Introduction
Elias M. Stein and Rami Shakarchi · 2003
Earlier work this paper cites.
Improved time bounds for near-optimal space Fourier representations
A. Gilbert, M. Muthukrishnan, and M. Strauss · 2005
Earlier work this paper cites.
Near optimal signal recovery from random projections: Universal encoding strategies
E. Candes and T. Tao · 2006
Earlier work this paper cites.
Compressed sensing
D. Donoho · 2006
Earlier work this paper cites.
SPGL1: A solver for large-scale sparse reconstruction, June 2007
E. van den Berg and M. P. Friedlander · 2007
Earlier work this paper cites.
Compressed sensing mri
M. Lustig, D.L. Donoho, J.M. Santos, and J.M. Pauly · 2008
Earlier work this paper cites.
On sparse reconstruction from Fourier and Gaussian measurements
M. Rudelson and R. Vershynin · 2008
Cited alongside, same era.
Probing the pareto frontier for basis pursuit solutions
E. van den Berg and M. P. Friedlander · 2008
Cited alongside, same era.
Advances in sparse signal recovery methods
Radu Berinde · 2009
Cited alongside, same era.
Sequential sparse matching pursuit
Radu Berinde and Piotr Indyk · 2009
Cited alongside, same era.
Deterministic sparse Fourier approximation via fooling arithmetic progressions
A. Akavia · 2010
Cited alongside, same era.
A probabilistic and ripless theory of compressed sensing
E. Candes and Y. Plan · 2010
Cited alongside, same era.
Faster gps via the sparse fourier transform
H. Hassanieh, F. Adib, D. Katabi, and P. Indyk · 2012
Later among the works it cites.
Near-optimal algorithm for sparse Fourier transform
H. Hassanieh, P. Indyk, D. Katabi, and E. Price · 2012
Later among the works it cites.
Simple and practical algorithm for sparse Fourier transform
H. Hassanieh, P. Indyk, D. Katabi, and E. Price · 2012
Later among the works it cites.
Improved approximation guarantees for sublinear-time Fourier algorithms
M.A. Iwen · 2012
Later among the works it cites.
Adaptive sub-linear time fourier algorithms
D. Lawlor, Y. Wang, and A. Christlieb · 2012
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Khanh Do Ba, Piotr Indyk, Eric Price, and David P. Woodruff · 2010
Cited alongside, same era.
Approximate sparse recovery: optimizing time and measurements
A. C. Gilbert, Y. Li, E. Porat, and M. J. Strauss · 2010
Cited alongside, same era.
Combinatorial sublinear-time Fourier algorithms
M. A. Iwen · 2010
Cited alongside, same era.
What does compressive sensing mean for X-ray CT and comparisons with its MRI application
Emil Sidky · 2011
Cited alongside, same era.
What’s the frequency, kenneth?: Sublinear fourier sampling off the grid
P. Boufounos, V. Cevher, A. C. Gilbert, Y. Li, and M. J. Strauss · 2012
Cited alongside, same era.
Universality in polytope phase transitions and message passing algorithms
M. Bayati, M. Lelarge, and A. Montanari · 2012
Cited alongside, same era.
Juhwan Yoo, S. Becker, M. Loh, M. Monge, E. Candès, and A. E-Neyestanak · 2012
Later among the works it cites.
A Mathematical Introduction to Compressive Sensing
Simon Foucart and Holger Rauhut · 2013
Later among the works it cites.
Sample-optimal average-case sparse fourier transform in two dimensions
Badih Ghazi, Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price, and Lixin Shi · 2013
Later among the works it cites.
A sparse prony fft
Sabine Heider, Stefan Kunis, Daniel Potts, and Michael Veit · 2013
Later among the works it cites.
Computing a k-sparse n-length discrete fourier transform using at most 4k samples and o (k log k) complexity
Sameer Pawar and Kannan Ramchandran · 2013
Later among the works it cites.
Sample-Optimal Fourier Sampling in Any Constant Dimension – Part II
Piotr Indyk and Michael Kapralov · 2014
Closest in time.
(Nearly) sample-optimal sparse fourier transform
Piotr Indyk, Michael Kapralov, and Eric Price · 2014
Closest in time.
A robust ffast framework for computing a k-sparse n-length dft in o(k log n) sample complexity using sparse-graph codes
Sameer Pawar and Kannan Ramchandran · 2014
Closest in time.