Fetching the paper…
Reading the bibliography…
We present the first sample-optimal sublinear time algorithms for the sparse Discrete Fourier Transform over a two-dimensional sqrt{n} x sqrt{n} grid.
Shift-register synthesis and bch decoding
J. Massey · 1969
Earlier work this paper cites.
The Theory of Error-Correcting Codes
F.J. MacWilliams and N.J.A. Sloane · 1977
Earlier work this paper cites.
A hard-corepredicate for allone-way functions
O. Goldreich and L. Levin · 1989
Earlier work this paper cites.
Interpolating polynomials from their values
R. Zippel · 1990
Earlier work this paper cites.
Learning decision trees using the Fourier spectrum
E. Kushilevitz and Y. Mansour · 1991
Earlier work this paper cites.
The JPEG still picture compression standard
G. Wallace · 1991
Earlier work this paper cites.
Randomized interpolation and approximation of sparse polynomials
Y. Mansour · 1992
Earlier work this paper cites.
Randomness and non-determinism
L.A. Levin · 1993
Earlier work this paper cites.
Image and video compression standards : algorithms and architectures
V. Bahskarna and K. Konstantinides · 1995
Earlier work this paper cites.
Digital video : an introduction to MPEG-2
B. G. Haskell, A. Puri, and A. N. Netravali · 1997
Earlier work this paper cites.
Algorithmic complexity in coding theory and the minimum distance problem
A. Vardy · 1997
Earlier work this paper cites.
Modern cryptography, probabilistic proofs and pseudorandomness
O. Goldreich · 1999
Cited alongside, same era.
Principles of Computerized Tomographic Imaging
A. Kak and M. Slaney · 2001
Cited alongside, same era.
Near-optimal sparse Fourier representations via sampling
A. Gilbert, S. Guha, P. Indyk, M. Muthukrishnan, and M. Strauss · 2002
Cited alongside, same era.
Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
V. Y. Pan · 2002
Cited alongside, same era.
Proving hard-core predicates using list decoding
A. Akavia, S. Goldwasser, and S. Safra · 2003
Cited alongside, same era.
Improved time bounds for near-optimal space Fourier representations
A. Gilbert, M. Muthukrishnan, and M. Strauss · 2005
Cited alongside, same era.
Deterministic sparse Fourier approximation via fooling arithmetic progressions
A. Akavia · 2010
Later among the works it cites.
Combinatorial sublinear-time Fourier algorithms
M. A. Iwen · 2010
Later among the works it cites.
Principles of Magnetic Resonance Imaging
D. Nishimura · 2010
Later among the works it cites.
( 1 + ϵ ) (1+\epsilon) -approximate sparse recovery
E. Price and D. P. Woodruff · 2011
Later among the works it cites.
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
Later among the works it cites.
Faster gps via the sparse fourier transform
H. Hassanieh, F. Adib, D. Katabi, and P. Indyk · 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…
Near optimal signal recovery from random projections: Universal encoding strategies
E. Candes and T. Tao · 2006
Cited alongside, same era.
Empirical evaluation of a sub-linear time sparse dft algorithm
M. A. Iwen, A. Gilbert, and M. Strauss · 2007
Cited alongside, same era.
A frame construction and a universal distortion bound for sparse representations
M. Akcakaya and V. Tarokh · 2008
Cited alongside, same era.
Why simple hash functions work: Exploiting the entropy in a data stream
M. Mitzenmacher and S. Vadhan · 2008
Cited alongside, same era.
Spectroscopy by integration of frequency and time domain information (sift) for fast acquisition of high resolution dark spectra
Y. Matsuki, M. Eddy, and J. Herzfeld · 2009
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.