Fetching the paper…
Reading the bibliography…
We give near-tight lower bounds for the sparsity required in several dimensionality reducing linear maps.
The widths of certain finite-dimensional sets and classes of smooth functions
Boris Sergeevich Kašin · 1977
Earlier work this paper cites.
On the widths of the Euclidean ball
Andrej Y. Garnaev and Efim D. Gluskin · 1984
Earlier work this paper cites.
Extensions of Lipschitz mappings into a Hilbert space
William B. Johnson and Joram Lindenstrauss · 1984
Earlier work this paper cites.
The Johnson-Lindenstrauss lemma and the sphericity of some graphs
Peter Frankl and Hiroshi Maehara · 1988
Earlier work this paper cites.
On Milman’s inequality and random subspaces which escape through a mesh in ℝ n \mathbb{R}^{n}
Yehoram Gordon · 1988
Earlier work this paper cites.
Approximate nearest neighbors: Towards removing the curse of dimensionality
Piotr Indyk and Rajeev Motwani · 1998
Earlier work this paper cites.
Algorithmic applications of low-distortion geometric embeddings
Piotr Indyk · 2001
Earlier work this paper cites.
Database-friendly random projections: Johnson-Lindenstrauss with binary coins
Dimitris Achlioptas · 2003
Earlier work this paper cites.
An elementary proof of a theorem of Johnson and Lindenstrauss
Sanjoy Dasgupta and Anupam Gupta · 2003
Earlier work this paper cites.
The random projection method
Santosh Vempala · 2004
Earlier work this paper cites.
Decoding by linear programming
Emmanuel J. Candès and Terence Tao · 2005
Earlier work this paper cites.
Empirical processes and random projections
Bo’az Klartag and Shahar Mendelson · 2005
Earlier work this paper cites.
The generic chaining: upper and lower bounds of stochastic processes
Michel Talagrand · 2005
Earlier work this paper cites.
A fast random sampling algorithm for sparsifying matrices
Sanjeev Arora, Elad Hazan, and Satyen Kale · 2006
Earlier work this paper cites.
An algorithmic theory of learning: Robust concepts and random projection
Rosa I. Arriaga and Santosh Vempala · 2006
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. Candès, Justin Romberg, and Terence Tao · 2006
Earlier work this paper cites.
Near-optimal signal recovery from random projections: universal encoding strategies?
Emmanuel J. Candès and Terence Tao · 2006
Earlier work this paper cites.
Compressed sensing
David L. Donoho · 2006
Cited alongside, same era.
Improved approximation algorithms for large matrices via random projections
Tamás Sarlós · 2006
Cited alongside, same era.
Sparse MRI: The application of compressed sensing for rapid MR Imaging
Michael Lustig, David Donoho, and John M. Pauly · 2007
Cited alongside, same era.
Signal recovery from random measurements via orthogonal matching pursuit
Joel A. Tropp and Anna C. Gilbert · 2007
Cited alongside, same era.
Iterative hard thresholding for compressed sensing
Thomas Blumensath and Mike E. Davies · 2008
Cited alongside, same era.
A simple proof of the restricted isometry property for random matrices
Richard Baraniuk, Mark Davenport, Ronald DeVore, and Michael Wakin · 2008
Cited alongside, same era.
Feature hashing for large scale multitask learning
Kilian Q. Weinberger, Anirban Dasgupta, John Langford, Alexander J. Smola, and Josh Attenberg · 2009
Later among the works it cites.
Lower bounds for sparse recovery
Khanh Do Ba, Piotr Indyk, Eric Price, and David P. Woodruff · 2010
Later among the works it cites.
Rademacher chaos, random Eulerian graphs and the sparse Johnson-Lindenstrauss transform
Vladimir Braverman, Rafail Ostrovsky, and Yuval Rabani · 2010
Later among the works it cites.
Sparse Graph Codes for Compression, Sensing, and Secrecy
Venkat B. Chandar · 2010
Later among the works it cites.
A sparse Johnson-Lindenstrauss transform
Anirban Dasgupta, Ravi Kumar, and Tamás Sarlós · 2010
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Practical near-optimal sparse recovery in the L1 norm
Radu Berinde, Piotr Indyk, and Milan Ružic · 2008
Cited alongside, same era.
The restricted isometry property and its implications for compressed sensing
Emmanuel J. Candès · 2008
Cited alongside, same era.
Near-optimal sparse recovery in the L1 norm
Piotr Indyk and Milan Ružic · 2008
Cited alongside, same era.
On variants of the Johnson-Lindenstrauss lemma
Jirí Matousek · 2008
Cited alongside, same era.
Large-scale parallel collaborative filtering for the netflix prize
Yunhong Zhou, Dennis M. Wilkinson, Robert Schreiber, and Rong Pan · 2008
Cited alongside, same era.
The Fast Johnson–Lindenstrauss transform and approximate nearest neighbors
Nir Ailon and Bernard Chazelle · 2009
Cited alongside, same era.
Daniel M. Kane and Jelani Nelson · 2010
Later among the works it cites.
Signal recovery from inaccurate and incomplete measurements via regularized orthogonal matching pursuit
Deanna Needell and Roman Vershynin · 2010
Later among the works it cites.
Almost optimal unrestricted fast Johnson-Lindenstrauss transform
Nir Ailon and Edo Liberty · 2011
Later among the works it cites.
Hard thresholding pursuit: an algorithm for compressive sensing
Simon Foucart · 2011
Later among the works it cites.
New and improved Johnson-Lindenstrauss embeddings via the Restricted Isometry Property
Felix Krahmer and Rachel Ward · 2011
Later among the works it cites.
Improved analysis of the subsampled randomized Hadamard transform
Joel A. Tropp · 2011
Later among the works it cites.
Low rank approximation and regression in input sparsity time
Kenneth L. Clarkson and David P. Woodruff · 2012
Closest in time.
Fast approximation of matrix coherence and statistical leverage
Petros Drineas, Malik Magdon-Ismail, Michael Mahoney, and David Woodruff · 2012
Closest in time.
Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit
David L. Donoho, Yaakov Tsaig, Iddo Drori, and Jean luc Starck · 2012
Closest in time.
Sparser Johnson-Lindenstrauss transforms
Daniel M. Kane and Jelani Nelson · 2012
Closest in time.
Xiangrui Meng and Michael W. Mahoney · 2012
Closest in time.
Iteratives approaches to row sampling
Gary L. Miller and Richard Peng · 2012
Closest in time.
OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings
Jelani Nelson and Huy L. Nguy e ^ ~ \tilde{\hat{\mbox{e}}} n · 2012
Closest in time.