Fetching the paper…
Reading the bibliography…
In this paper we revisit the deterministic version of the Sparse Fourier Transform problem, which asks to read only a few entries of $x \in \mathbb{C}^n$ and design a recovery algorithm such that the output of the algorithm approximates $\hat x$, the Discrete Fourier Transform (DFT) of $x$.
On character sums and primitive roots
David A. Burgess · 1962
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.
A Classical Introduction to Modern Number Theory
Kenneth Ireland and Michael Rosen · 1990
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.
Hardness vs randomness
Noam Nisan and Avi Wigderson · 1994
Earlier work this paper cites.
Additive Number Theory The Classical Bases
Melvyn B. Nathanson · 1996
Earlier work this paper cites.
The best of the 20th century: Editors name top 10 algorithms
Barry A Cipra · 2000
Earlier work this paper cites.
Extractors and pseudorandom generators
Luca Trevisan · 2001
Earlier work this paper cites.
Incomplete additive character sums and applications
Arne Winterhof · 2001
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.
Improved time bounds for near-optimal sparse Fourier representations
Anna C Gilbert, S Muthukrishnan, and Martin Strauss · 2005
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.
Compressed sensing
David L. Donoho · 2006
Earlier work this paper cites.
Additive combinatorics
Terence Tao and Van H Vu · 2006
Earlier work this paper cites.
Deterministic constructions of compressed sensing matrices
Ronald A DeVore · 2007
Earlier work this paper cites.
Bounds on exponential sums over small multiplicative subgroups
Pär Kurlberg · 2007
Earlier work this paper cites.
Lower bounds on frequency estimation of data streams
Sumit Ganguly · 2008
Earlier work this paper cites.
A deterministic sub-linear time sparse Fourier algorithm via non-adaptive compressed sensing methods
Mark A Iwen · 2008
Earlier work this paper cites.
Explicit non-adaptive combinatorial group testing schemes
Ely Porat and Amir Rothschild · 2008
Earlier work this paper cites.
Perturbed identity matrices have high rank: Proof and applications
Noga Alon · 2009
Earlier work this paper cites.
Compressed sensing and best k k -term approximation
Albert Cohen, Wolfgang Dahmen, and Ronald DeVore · 2009
Cited alongside, same era.
Deterministic sparse Fourier approximation via fooling arithmetic progressions
Adi Akavia · 2010
Cited alongside, same era.
Lower bounds for sparse recovery
Khanh Do Ba, Piotr Indyk, Eric Price, and David P Woodruff · 2010
Cited alongside, same era.
The gelfand widths of ℓ p \ell_{p} -balls for 0 < p ≤ 1 0<p\leq 1
Simon Foucart, Alain Pajor, Holger Rauhut, and Tino Ullrich · 2010
Cited alongside, same era.
Approximate sparse recovery: optimizing time and measurements
Anna C Gilbert, Yi Li, Ely Porat, and Martin J Strauss · 2010
Cited alongside, same era.
Combinatorial sublinear-time Fourier algorithms
Mark A Iwen · 2010
Cited alongside, same era.
On deterministic sketching and streaming for sparse recovery and norm estimation
Jelani Nelson, Huy L Nguyên, and David P Woodruff · 2014
Later among the works it cites.
A robust R-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
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.
An introduction to matrix concentration inequalities
Joel A. Tropp · 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…
Deterministic construction of binary, bipolar, and ternary compressed sensing matrices
Arash Amini and Farokh Marvasti · 2011
Cited alongside, same era.
Breaking the k 2 k^{2} barrier for explicit RIP matrices
Jean Bourgain, Stephen J Dilworth, Kevin Ford, Sergei V Konyagin, and Denka Kutzarova · 2011
Cited alongside, same era.
On the power of adaptivity in sparse recovery
Piotr Indyk, Eric Price, and David P Woodruff · 2011
Cited alongside, same era.
(1+ eps)-approximate sparse recovery
Eric Price and David P Woodruff · 2011
Cited alongside, same era.
Deterministic sampling of sparse trigonometric polynomials
Zhiqiang Xu · 2011
Cited alongside, same era.
Nearly optimal sparse Fourier transform
Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price · 2012
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.
Discrete uncertainty principles and sparse signal processing
Afonso S Bandeira, Megan E Lewis, and Dustin G Mixon · 2017
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.
An adaptive sublinear-time block sparse Fourier transform
Volkan Cevher, Michael Kapralov, Jonathan Scarlett, and Amir Zandieh · 2017
Later among the works it cites.
For-all sparse recovery in near-optimal time
Anna C Gilbert, Yi Li, Ely Porat, and Martin J Strauss · 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.
Explicit, almost optimal, epsilon-balanced codes
Amnon Ta-Shma · 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 · 2018
Later among the works it cites.
Deterministic heavy hitters with sublinear query time
Yi Li and Vasileios Nakos · 2018
Later among the works it cites.
On low-risk heavy hitters and sparse recovery schemes
Yi Li, Vasileios Nakos, and David P. Woodruff · 2018
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 · 2018
Later among the works it cites.
Improved algorithms for adaptive compressed sensing
Vasileios Nakos, Xiaofei Shi, David P. Woodruff, and Hongyang Zhang · 2018
Later among the works it cites.
Dimension-independent sparse Fourier transform
Michael Kapralov, Ameya Velingker, and Amir Zandieh · 2019
Closest in time.
Stronger l 2 {}_{\mbox{2}} /l 2 {}_{\mbox{2}} compressed sensing; without iterating
Vasileios Nakos and Zhao Song · 2019
Closest in time.
(nearly) sample-optimal sparse fourier transform in any dimension; ripless and filterless
Vasileios Nakos, Zhao Song, and Zhengyu Wang · 2019
Closest in time.