Fetching the paper…
Reading the bibliography…
We consider the problem of computing a $k$-sparse approximation to the Fourier transform of a length $N$ signal.
A hard-corepredicate for allone-way functions
O. Goldreich and L. Levin · 1989
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.
Fast fourier transforms for nonequispaced data
A. Dutt and V. Rokhlin · 1993
Earlier work this paper cites.
The Best of the 20th Century: Editors Name Top 10 Algorithms
B. A. Cipra · 2000
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.
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.
Compressed sensing mri
M. Lustig, D.L. Donoho, J.M. Santos, and J.M. Pauly · 2008
Cited alongside, same era.
On sparse reconstruction from Fourier and Gaussian measurements
M. Rudelson and R. Vershynin · 2008
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.
Lower Bounds for Sparse Recovery
K. Do Ba, P. Indyk, E. Price, and D. 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.
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.
Sample-optimal average-case sparse Fourier transform in two dimensions
B. Ghazi, H. Hassanieh, P. Indyk, D. Katabi, E. Price, and L. Shi · 2013
Later among the works it cites.
A sparse Prony FFT
S. Heider, S. Kunis, D. Potts, and M. Veit · 2013
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
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.
Restricted isometry of Fourier matrices and list decodability of random linear codes
M. Cheraghchi, V. Guruswami, and A. Velingker · 2012
Cited alongside, same era.
Faster GPS via the Sparse Fourier Transform
H. Hassanieh, F. Adib, D. Katabi, and P. Indyk · 2012
Cited alongside, same era.
Computing a k k -sparse n n -length Discrete Fourier Transform using at most 4 k 4k samples and O ( k l o g k ) O(klogk) complexity
S. Pawar and K. Ramchandran
Cited in the paper.
Later among the works it cites.
An improved estimate in the restricted isometry problem
J. Bourgain · 2014
Later among the works it cites.
Sample-optimal Fourier sampling in any fixed dimension
P. Indyk and M. Kapralov · 2014
Later among the works it cites.
(Nearly) sample-optimal sparse Fourier transform
P. Indyk, M. Kapralov, and E. Price · 2014
Later among the works it cites.
A robust sparse Fourier transform in the continuous setting
E. Price and Z. Song · 2015
Later among the works it cites.
The restricted isometry property of subsampled fourier matrices
I. Haviv and O. Regev · 2016
Closest in time.