Fetching the paper…
Reading the bibliography…
We give two different and simple constructions for dimensionality reduction in $\ell_2$ via linear mappings that are sparse: only an $O(\varepsilon)$-fraction of entries in each column of our embedding matrices are non-zero to achieve distortion $1+\varepsilon$ with high probability, while still achieving the asymptotically optimal number of rows.
Characteristic vectors of bordered matrices with infinite dimensions
Eugene P. Wigner · 1955
Earlier work this paper cites.
A bound on tail probabilities for quadratic forms in independent random variables
David Lee Hanson and Farroll Tim Wright · 1971
Earlier work this paper cites.
Universal classes of hash functions
J. Lawrence Carter and Mark N. Wegman · 1979
Earlier work this paper cites.
The eigenvalues of random symmetric matrices
Zoltán Füredi and János Komlós · 1981
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.
Randomized Algorithms
Rajeev Motwani and Prabakar Raghavan · 1995
Earlier work this paper cites.
Modern Computer Algebra
Joachim von zur Gathen and Jürgen Gerhard · 1999
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.
Problems and results in extremal combinatorics I
Noga Alon · 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.
Finding frequent items in data streams
Moses Charikar, Kevin Chen, and Martin Farach-Colton · 2004
Earlier work this paper cites.
The random projection method
Santosh Vempala · 2004
Earlier work this paper cites.
Introduction to Data Mining
Vipin Kumar Pang-Ning Tan, Michael Steinbach · 2005
Cited alongside, same era.
An algorithmic theory of learning: Robust concepts and random projection
Rosa I. Arriaga and Santosh Vempala · 2006
Cited alongside, same era.
Improved approximation algorithms for large matrices via random projections
Tamás Sarlós · 2006
Cited alongside, same era.
On variants of the Johnson-Lindenstrauss lemma
Jirí Matousek · 2008
Cited alongside, same era.
The fast Johnson–Lindenstrauss transform and approximate nearest neighbors
Nir Ailon and Bernard Chazelle · 2009
Cited alongside, same era.
Fast dimension reduction using Rademacher series on dual BCH codes
Nir Ailon and Edo Liberty · 2009
Cited alongside, same era.
Almost optimal explicit Johnson-Lindenstrauss transformations
Daniel M. Kane, Raghu Meka, and Jelani Nelson · 2011
Closest in time.
Fast moment estimation in data streams in optimal space
Daniel M. Kane, Jelani Nelson, Ely Porat, and David P. Woodruff · 2011
Closest in time.
New and improved Johnson-Lindenstrauss embeddings via the Restricted Isometry Property
Felix Krahmer and Rachel Ward · 2011
Closest in time.
A variant of the Johnson-Lindenstrauss lemma for circulant matrices
Jan Vybíral · 2011
Closest in time.
Approximate nearest neighbor: Towards removing the curse of dimensionality
Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani · 2012
Closest in time.
Sparser Johnson-Lindenstrauss transforms
Daniel M. Kane and Jelani Nelson · 2012
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Numerical linear algebra in the streaming model
Kenneth L. Clarkson and David P. Woodruff · 2009
Cited alongside, same era.
Derandomized constructions of k
Eyal Kaplan, Moni Naor, and Omer Reingold · 2009
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
Cited alongside, same era.
Rademacher chaos, random Eulerian graphs and the sparse Johnson-Lindenstrauss transform
Vladimir Braverman, Rafail Ostrovsky, and Yuval Rabani · 2010
Cited alongside, same era.
A sparse Johnson-Lindenstrauss transform
Anirban Dasgupta, Ravi Kumar, and Tamás Sarlós · 2010
Cited alongside, same era.
A derandomized sparse Johnson-Lindenstrauss transform
Daniel M. Kane and Jelani Nelson · 2010
Cited alongside, same era.
Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation
Mikkel Thorup and Yin Zhang · 2012
Closest in time.
An almost optimal unrestricted fast Johnson-Lindenstrauss transform
Nir Ailon and Edo Liberty · 2013
Closest in time.
Low rank approximation and regression in input sparsity time
Kenneth L. Clarkson and David P. Woodruff · 2013
Closest in time.
Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with subconstant error
T. S. Jayram and David P. Woodruff · 2013
Closest in time.
Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
Xiangrui Meng and Michael W. Mahoney · 2013
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 · 2013
Closest in time.
Sparsity lower bounds for dimensionality reducing maps
Jelani Nelson and Huy L. Nguy e ^ ~ \tilde{\hat{\mbox{e}}} n · 2013
Closest in time.