Fetching the paper…
Reading the bibliography…
In this paper, we consider the extensively studied problem of computing a $k$-sparse approximation to the $d$-dimensional Fourier transform of a length $n$ signal.
An algorithm for the machine calculation of complex Fourier series
James W Cooley and John W Tukey · 1965
Earlier work this paper cites.
A hard-core predicate for all one-way functions
Oded Goldreich and Leonid A Levin · 1989
Earlier work this paper cites.
The New Physical Optics Notebook: Tutorials in Fourier Optics
George O Reynolds · 1989
Earlier work this paper cites.
Randomized interpolation and approximation of sparse polynomials
Yishay Mansour · 1992
Earlier work this paper cites.
Learning decision trees using the Fourier spectrum
Eyal Kushilevitz and Yishay Mansour · 1993
Earlier work this paper cites.
Finding frequent items in data streams
Moses Charikar, Kevin Chen, and Martin Farach-Colton · 2002
Earlier work this paper cites.
Near-optimal sparse Fourier representations via sampling
Anna C Gilbert, Sudipto Guha, Piotr Indyk, S Muthukrishnan, and Martin Strauss · 2002
Earlier work this paper cites.
Proving hard-core predicates using list decoding
Adi Akavia, Shafi Goldwasser, and Shmuel Safra · 2003
Earlier work this paper cites.
Decoding by linear programming
Emmanuel Candes and Terence Tao · 2005
Earlier work this paper cites.
Improved time bounds for near-optimal sparse Fourier representations
Anna C Gilbert, S Muthukrishnan, and Martin Strauss · 2005
Earlier work this paper cites.
Introduction to Fourier optics
Joseph W Goodman · 2005
Earlier work this paper cites.
Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information
Emmanuel J Candès, Justin Romberg, and Terence Tao · 2006
Earlier work this paper cites.
Stable signal recovery from incomplete and inaccurate measurements
Emmanuel J Candes, Justin K Romberg, and Terence Tao · 2006
Earlier work this paper cites.
Near-optimal signal recovery from random projections: Universal encoding strategies?
Emmanuel J Candes and Terence Tao · 2006
Earlier work this paper cites.
Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit
David Leigh Donoho, Iddo Drori, Yaakov Tsaig, and Jean-Luc Starck · 2006
Earlier work this paper cites.
Compressed sensing
David L. Donoho · 2006
Earlier work this paper cites.
Signal recovery from partial information via orthogonal matching pursuit
Joel Tropp and Anna C Gilbert · 2007
Earlier work this paper cites.
MRI reconstruction using discrete Fourier transform: a tutorial
Abiodun M Aibinu, Momoh JE Salami, Amir A Shafie, and Athaur Rahman Najeeb · 2008
Earlier work this paper cites.
Iterative thresholding for sparse approximations
Thomas Blumensath and Mike E Davies · 2008
Earlier work this paper cites.
Subspace pursuit for compressive sensing: Closing the gap between performance and complexity
Wei Dai and Olgica Milenkovic · 2008
Earlier work this paper cites.
A deterministic sub-linear time sparse Fourier algorithm via non-adaptive compressed sensing methods
Mark A Iwen · 2008
Cited alongside, same era.
On sparse reconstruction from Fourier and Gaussian measurements
Mark Rudelson and Roman Vershynin · 2008
Cited alongside, same era.
Iterative hard thresholding for compressed sensing
Thomas Blumensath and Mike E Davies · 2009
Cited alongside, same era.
A simple, efficient and near optimal algorithm for compressed sensing
Thomas Blumensath and Mike E Davies · 2009
Cited alongside, same era.
Compressed sensing and best k k -term approximation
Albert Cohen, Wolfgang Dahmen, and Ronald DeVore · 2009
Cited alongside, same era.
Gradient descent with sparsification: an iterative algorithm for sparse recovery with restricted isometry property
Rahul Garg and Rohit Khandekar · 2009
Sample-optimal Fourier sampling in any constant dimension
Piotr Indyk and Michael Kapralov · 2014
Later among the works it cites.
(Nearly) Sample-optimal sparse Fourier transform
Piotr Indyk, Michael Kapralov, and Eric Price · 2014
Later among the works it cites.
A robust R-FFAST framework for computing a k k -sparse n n -length DFT in O ( k log n ) {O}(k\log n) sample complexity using sparse-graph codes
Sameer Pawar and Kannan Ramchandran · 2014
Later among the works it cites.
A robust sparse Fourier transform in the continuous setting
Eric Price and Zhao Song · 2015
Later among the works it cites.
Fourier-sparse interpolation without a frequency gap
Xue Chen, Daniel M Kane, Eric Price, and Zhao Song · 2016
Later among the works it cites.
The restricted isometry property of subsampled Fourier matrices
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
Deanna Needell and Joel A Tropp · 2009
Cited alongside, same era.
Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
Deanna Needell and Roman Vershynin · 2009
Cited alongside, same era.
Normalized iterative hard thresholding: Guaranteed stability and performance
Thomas Blumensath and Mike E Davies · 2010
Cited alongside, same era.
Combinatorial sublinear-time Fourier algorithms
Mark A Iwen · 2010
Cited alongside, same era.
Signal recovery from inaccurate and incomplete measurements via regularized orthogonal matching pursuit
D Needel and R Vershynin · 2010
Cited alongside, same era.
Hard thresholding pursuit: an algorithm for compressive sensing
Simon Foucart · 2011
Cited alongside, same era.
Ishay Haviv and Oded Regev · 2016
Later among the works it cites.
Sparse Fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time
Michael Kapralov · 2016
Later among the works it cites.
A deterministic sparse FFT for functions with structured Fourier sparsity
Sina Bittens, Ruochuan Zhang, and Mark A Iwen · 2017
Later among the works it cites.
Nearly optimal deterministic algorithm for sparse walsh-hadamard transform
Mahdi Cheraghchi and Piotr Indyk · 2017
Later among the works it cites.
Sample efficient estimation and recovery in sparse FFT via isolation on average
Michael Kapralov · 2017
Later among the works it cites.
A new class of fully discrete sparse Fourier transforms: Faster stable implementations with guarantees
Sami Merhi, Ruochuan Zhang, Mark A Iwen, and Andrew Christlieb · 2017
Later among the works it cites.
High dimensional Fourier transform in the continuous setting
Zhao Song · 2017
Later among the works it cites.
A universal sampling method for reconstructing signals with simple fourier transforms
Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh · 2019
Closest in time.
Sparse reconstruction from hadamard matrices: A lower bound
Jaroslaw Blasiok, Patrick Lopatto, Kyle Luh, and Jake Marcinek · 2019
Closest in time.
Active regression via linear-sample sparsification
Xue Chen and Eric Price · 2019
Closest in time.
Estimating the frequency of a clustered signal
Xue Chen and Eric Price · 2019
Closest in time.
Dimension-independent sparse Fourier transform
Michael Kapralov, Ameya Velingker, and Amir Zandieh · 2019
Closest in time.
Deterministic sparse Fourier transform with an ℓ ∞ \ell_{\infty} guarantee
Yi Li and Vasileios Nakos · 2019
Closest in time.
Improved lower bounds for the restricted isometry property of subsampled fourier matrices
Sharavas Rao · 2019
Closest in time.
Matrix Theory : Optimization, Concentration and Algorithms
Zhao Song · 2019
Closest in time.