An Improved Lower Bound for Sparse Reconstruction from Subsampled Walsh Matrices

Mahdi Cheraghchi, Venkatesan Guruswami, and Ameya Velingker, Restricted isometry of Fourier matrices and list decodability of random linear codes , SIAM J. Comput. 42

1914

Earlier work this paper cites.

Boris Sergeevich Kashin, Diameters of some finite-dimensional sets and classes of smooth functions , Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya 41

1977

Earlier work this paper cites.

Andrej Y. Garnaev and Efim D. Gluskin, On widths of the euclidean ball , Soviet Mathematics Doklady, vol. 277, 1984, pp. 1048–1052

1984

Earlier work this paper cites.

Audrey Terras, Fourier analysis on finite groups and applications , London Mathematical Society Student Texts, vol. 43, Cambridge University Press, Cambridge, 1999

1999

Earlier work this paper cites.

Emmanuel J. Candès and Terence Tao, Near-optimal signal recovery from random projections: Universal encoding strategies? , IEEE transactions on information theory 52

2006

Earlier work this paper cites.

Mark Rudelson and Roman Vershynin, On sparse reconstruction from Fourier and Gaussian measurements , Communications on Pure and Applied Mathematics 61

2008

Cited alongside, same era.

Khanh Do Ba, Piotr Indyk, Eric Price, and David P Woodruff, Lower bounds for sparse recovery , Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, SIAM, 2010, pp. 1190–1197

2010

Cited alongside, same era.

Holger Rauhut, Compressive sensing and structured random matrices , Theoretical foundations and numerical methods for sparse recovery 9

2010

Cited alongside, same era.

Simon Foucart and Holger Rauhut, A mathematical introduction to compressive sensing , Applied and Numerical Harmonic Analysis, Birkhäuser/Springer, New York, 2013

2013

Cited alongside, same era.

Jelani Nelson and Huy L. Nguyen, Sparsity lower bounds for dimensionality reducing maps , Proceedings of the forty-fifth annual ACM symposium on Theory of computing, ACM, 2013, pp. 101–110

Jean Bourgain, An improved estimate in the restricted isometry problem , Geometric aspects of functional analysis, Lecture Notes in Math., vol. 2116, Springer, Cham, 2014, pp. 65–70

2014

Later among the works it cites.

Sjoerd Dirksen, Tail bounds via generic chaining , Electronic Journal of Probability 20

2015

Later among the works it cites.

Noga Alon and Joel H. Spencer, The probabilistic method , fourth ed., Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2016

2016

Later among the works it cites.

Afonso S. Bandeira, Megan E. Lewis, and Dustin G. Mixon, Discrete uncertainty principles and sparse signal processing , Journal of Fourier Analysis and Applications (2017), 1–22

2017

Later among the works it cites.

Ishay Haviv and Oded Regev, The restricted isometry property of subsampled fourier matrices , Geometric Aspects of Functional Analysis, Springer, 2017, pp. 163–179