Fetching the paper…
Reading the bibliography…
An "oblivious subspace embedding (OSE)" given some parameters eps,d is a distribution D over matrices B in R^{m x n} such that for any linear subspace W in R^n with dim(W) = d it holds that Pr_{B ~ D}(forall x in W ||B x||_2 in (1 +/- eps)||x||_2) > 2/3 We show an OSE exists with m = O(d^2/eps^2) and where every B in the support of D has exactly s=1 non-zero entries per column.
Edge-disjoint spanning trees of finite graphs
Crispin St. John Alvah Nash-Williams · 1961
Earlier work this paper cites.
On the problem of decomposing a graph into n n connected factors
William Thomas Tutte · 1961
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.
Unitäre transformationen großer matrizen
Arnold Schönhage · 1973
Earlier work this paper cites.
Triangular factorization and inversion by fast matrix multiplication
James R. Bunch and John E. Hopcroft · 1974
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.
Limit of the smallest eigenvalue of a large dimensional sample covariance matrix
Z.D. Bai and Y.Q. Yin · 1993
Earlier work this paper cites.
Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs
Noga Alon and Van H. Vu · 1997
Earlier work this paper cites.
Database-friendly random projections: Johnson-Lindenstrauss with binary coins
Dimitris Achlioptas · 2003
Earlier work this paper cites.
Improved approximation algorithms for large matrices via random projections
Tamás Sarlós · 2006
Earlier work this paper cites.
Fast linear algebra is stable
James Demmel, Ioana Dumitriu, and Olga Holtz · 2007
Earlier work this paper cites.
Matchings, Matroids and Submodular Functions
Nicholas J. A. Harvey · 2008
Earlier work this paper cites.
Large-scale parallel collaborative filtering for the netflix prize
Yunhong Zhou, Dennis M. Wilkinson, Robert Schreiber, and Rong Pan · 2008
Earlier work this paper cites.
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.
Numerical linear algebra in the streaming model
Kenneth L. Clarkson and David P. Woodruff · 2009
Cited alongside, same era.
A fast and efficient algorithm for low-rank approximation of a matrix
Nam H. Nguyen, Thong T. Do, and Trac D. Tran · 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
Improved analysis of the subsampled randomized Hadamard transform
Joel A. Tropp · 2011
Later among the works it cites.
A variant of the Johnson-Lindenstrauss lemma for circulant matrices
Jan Vybíral · 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.
Suprema of chaos processes and the restricted isometry property
Felix Krahmer, Shahar Mendelson, and Holger Rauhut · 2012
Closest in time.
Sparser Johnson-Lindenstrauss transforms
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
A derandomized sparse Johnson-Lindenstrauss transform
Daniel M. Kane and Jelani Nelson · 2010
Cited alongside, same era.
Almost optimal unrestricted fast Johnson-Lindenstrauss transform
Nir Ailon and Edo Liberty · 2011
Cited alongside, same era.
Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
Nathan Halko, Per-Gunnar Martinsson, and Joel A. Tropp · 2011
Cited alongside, same era.
Johnson-lindenstrauss lemma for circulant matrices
Aicke Hinrichs and Jan Vybíral · 2011
Cited alongside, same era.
Fast moment estimation in data streams in optimal space
Daniel M. Kane, Jelani Nelson, Ely Porat, and David P. Woodruff · 2011
Cited alongside, same era.
New and improved Johnson-Lindenstrauss embeddings via the Restricted Isometry Property
Felix Krahmer and Rachel Ward · 2011
Cited alongside, same era.
Daniel M. Kane and Jelani Nelson · 2012
Closest in time.
Sparsity lower bounds for dimensionality-reducing maps
Jelani Nelson and Huy L. Nguy e ^ ~ \tilde{\hat{\mbox{e}}} n · 2012
Closest in time.
Topics in random matrix theory
Terence Tao · 2012
Closest in time.
Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation
Mikkel Thorup and Yin Zhang · 2012
Closest in time.
Introduction to the non-asymptotic analysis of random matrices
Roman Vershynin · 2012
Closest in time.
Multiplying matrices faster than Coppersmith-Winograd
Virginia Vassilevska Williams · 2012
Closest in time.
Fast matrix rank algorithms and applications
Ho yee Cheung, Tsz Chiu Kwok, and Lap Chi Lau · 2012
Closest in time.