Fetching the paper…
Reading the bibliography…
We prove, using the subspace embedding guarantee in a black box way, that one can achieve the spectral norm guarantee for approximate matrix multiplication with a dimensionality-reducing map having $m = O(\tilde{r}/\varepsilon^2)$ rows.
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.
Extensions of Lipschitz mappings into a Hilbert space
William B. Johnson and Joram Lindenstrauss · 1984
Earlier work this paper cites.
Inégalités de Khintchine dans C p {C_{p}} ( 1 < p < ∞ ) (1<p<\infty)
François Lust-Piquard · 1986
Earlier work this paper cites.
Noncommutative Khintchine and Paley inequalities
François Lust-Piquard and Gilles Pisier · 1991
Earlier work this paper cites.
Strong converse for identification via quantum channels
Rudolf Ahlswede and Andreas J. Winter · 2002
Earlier work this paper cites.
Finding frequent items in data streams
Moses Charikar, Kevin C. Chen, and Martin Farach-Colton · 2004
Earlier work this paper cites.
Fast Monte Carlo algorithms for matrices I: approximating matrix multiplication
Petros Drineas, Ravi Kannan, and Michael W. Mahoney · 2006
Earlier work this paper cites.
Sampling algorithms for ℓ 2 \ell_{2} regression and applications
Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan · 2006
Earlier work this paper cites.
Improved approximation algorithms for large matrices via random projections
Tamás Sarlós · 2006
Earlier work this paper cites.
Randomized algorithms for the low-rank approximation of matrices
Edo Liberty, Franco Woolfe, Per-Gunnar Martinsson, Vladimir Rokhlin, and Mark Tygert · 2007
Earlier work this paper cites.
The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
Nir Ailon and Bernard Chazelle · 2009
Earlier work this paper cites.
Numerical linear algebra in the streaming model
Kenneth L. Clarkson and David P. Woodruff · 2009
Earlier work this paper cites.
Multiclass support vector classification via coding and regression
Pei-Chun Chen, Kuang-Yao Lee, Tsung-Ju Lee, Yuh-Jye Lee, and Su-Yun Huang · 2010
Earlier work this paper cites.
A sparse Johnson-Lindenstrauss transform
Anirban Dasgupta, Ravi Kumar, and Tamás Sarlós · 2010
Earlier work this paper cites.
Subgraph sparsification and nearly optimal ultrasparsifiers
Alexandra Kolla, Yury Makarychev, Amin Saberi, and Shang-Hua Teng · 2010
Earlier work this paper cites.
Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
Nathan Halko, Per-Gunnar Martinsson, and Joel A. Tropp · 2011
Earlier work this paper cites.
Almost optimal explicit johnson-lindenstrauss families
Daniel M. Kane, Raghu Meka, and Jelani Nelson · 2011
Earlier work this paper cites.
New and improved Johnson-Lindenstrauss embeddings via the Restricted Isometry Property
Felix Krahmer and Rachel Ward · 2011
Cited alongside, same era.
Randomized algorithms for matrices and data
Michael W. Mahoney · 2011
Cited alongside, same era.
Low rank matrix-valued Chernoff bounds and approximate matrix multiplication
Avner Magen and Anastasios Zouzias · 2011
Cited alongside, same era.
New probabilistic bounds on eigenvalues and eigenvectors of random kernel matrices
Nima Reyhani, Hideitsu Hino, and Ricardo Vigário · 2011
Cited alongside, same era.
Graph sparsification by effective resistances
Daniel A. Spielman and Nikhil Srivastava · 2011
Cited alongside, same era.
Improved analysis of the subsampled randomized Hadamard transform
Joel A. Tropp · 2011
Cited alongside, same era.
Hanson-Wright inequality and sub-gaussian concentration
Mark Rudelson and Roman Vershynin · 2013
Later among the works it cites.
An improved estimate in the restricted isometry problem
Jean Bourgain · 2014
Later among the works it cites.
Sparser Johnson-Lindenstrauss transforms
Daniel M. Kane and Jelani Nelson · 2014
Later among the works it cites.
Approximate matrix multiplication with application to linear embeddings
Anastasios T. Kyrillidis, Michail Vlachos, and Anastasios Zouzias · 2014
Later among the works it cites.
Improved distributed principal component analysis
Yingyu Liang, Maria-Florina Balcan, Vandana Kanchanapally, and David P. Woodruff · 2014
Later among the works it cites.
Lower bounds for oblivious subspace embeddings
Jelani Nelson and Huy L. Nguy e ^ ~ \tilde{\hat{\mbox{e}}} n · 2014
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Twice-Ramanujan sparsifiers
Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava · 2012
Cited alongside, same era.
Fast approximation of matrix coherence and statistical leverage
Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, and David P. Woodruff · 2012
Cited alongside, same era.
Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation
Mikkel Thorup and Yin Zhang · 2012
Cited alongside, same era.
An almost optimal unrestricted fast Johnson-Lindenstrauss transform
Nir Ailon and Edo Liberty · 2013
Cited alongside, same era.
Low rank approximation and regression in input sparsity time
Kenneth L. Clarkson and David P. Woodruff · 2013
Cited alongside, same era.
A Mathematical Introduction to Compressive Sensing
Simon Foucart and Holger Rauhut · 2013
Cited alongside, same era.
Later among the works it cites.
New constructions of RIP matrices with fast multiplication and fewer rows
Jelani Nelson, Eric Price, and Mary Wootters · 2014
Later among the works it cites.
Sketching as a tool for numerical linear algebra
David P. Woodruff · 2014
Later among the works it cites.
Randomized dimensionality reduction for k-means clustering
Christos Boutsidis, Anastasios Zouzias, Michael W. Mahoney, and Petros Drineas · 2015
Closest in time.
Dimensionality reduction for k-means clustering and low rank approximation
Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Mădălina Persu · 2015
Closest in time.
Uniform sampling for matrix approximation
Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford · 2015
Closest in time.
Constructing linear sized spectral sparsification in almost linear time
Yin Tat Lee and He Sun · 2015
Closest in time.
An introduction to matrix concentration inequalities
Joel A Tropp · 2015
Closest in time.
Randomized sketches for kernels: Fast and optimal non-parametric regression
Yun Yang, Mert Pilanci, and Martin J. Wainwright · 2015
Closest in time.
Simpler and tighter analysis of sparse oblivious subspace embeddings
Michael B. Cohen · 2016
Closest in time.
The restricted isometry property of subsampled Fourier matrices
Ishay Haviv and Oded Regev · 2016
Closest in time.