Fetching the paper…
Reading the bibliography…
We design a new distribution over $\poly(r \eps^{-1}) \times n$ matrices $S$ so that for any fixed $n \times d$ matrix $A$ of rank $r$, with probability at least 9/10, $\norm{SAx}_2 = (1 \pm \eps)\norm{Ax}_2$ simultaneously for all $x \in \mathbb{R}^d$.
A bound on tail probabilities for quadratic forms in independent random variables
D.L. Hanson and F.T. Wright · 1971
Earlier work this paper cites.
Matrix computations (3. ed.)
Gene H. Golub and Charles F. van Loan · 1996
Earlier work this paper cites.
Numerical linear algebra
Lloyd N. Trefethen and David Bau · 1997
Earlier work this paper cites.
Authoritative sources in a hyperlinked environment
Jon M. Kleinberg · 1999
Earlier work this paper cites.
Random vectors in the isotropic position
M. Rudelson · 1999
Earlier work this paper cites.
Latent semantic indexing: A probabilistic analysis
Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, and Santosh Vempala · 2000
Earlier work this paper cites.
Web search via hub synthesis
Dimitris Achlioptas, Amos Fiat, Anna R. Karlin, and Frank McSherry · 2001
Earlier work this paper cites.
Spectral analysis of data
Yossi Azar, Amos Fiat, Anna R. Karlin, Frank McSherry, and Jared Saia · 2001
Earlier work this paper cites.
Spectral partitioning of random graphs
Frank McSherry · 2001
Earlier work this paper cites.
Competitive recommendation systems
Petros Drineas, Iordanis Kerenidis, and Prabhakar Raghavan · 2002
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.
Clustering large graphs via the singular value decomposition
Petros Drineas, Alan M. Frieze, Ravi Kannan, Santosh Vempala, and V. Vinay · 2004
Earlier work this paper cites.
Fast Monte-Carlo algorithms for finding low-rank approximations
Alan M. Frieze, Ravi Kannan, and Santosh Vempala · 2004
Earlier work this paper cites.
Tabulation based 4-universal hashing with applications to second moment estimation
Mikkel Thorup and Yin Zhang · 2004
Earlier work this paper cites.
On spectral learning of mixtures of distributions
Dimitris Achlioptas and Frank McSherry · 2005
Earlier work this paper cites.
Approximating a Gram matrix for improved kernel-based learning
Petros Drineas and Michael W. Mahoney · 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.
Matrix approximation and projective clustering via volume sampling
Amit Deshpande, Luis Rademacher, Santosh Vempala, and Grant Wang · 2006
Earlier work this paper cites.
Adaptive sampling and fast low-rank matrix approximation
Amit Deshpande and Santosh Vempala · 2006
Cited alongside, same era.
Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication
Petros Drineas, Ravi Kannan, and Michael W. Mahoney · 2006
Cited alongside, same era.
Fast Monte Carlo algorithms for matrices II: Computing a low-rank approximation to a matrix
Petros Drineas, Ravi Kannan, and Michael W. Mahoney · 2006
Cited alongside, same era.
Fast Monte Carlo algorithms for matrices III: Computing a compressed approximate matrix decomposition
Petros Drineas, Ravi Kannan, and Michael W. Mahoney · 2006
Cited alongside, same era.
Sampling algorithms for ℓ 2 \ell_{2} regression and applications
Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan · 2006
Cited alongside, same era.
Subspace sampling and relative-error matrix approximation: Column-based methods
A sparser Johnson-Lindenstrauss transform
Daniel M. Kane and Jelani Nelson · 2010
Later among the works it cites.
Fast Manhattan sketches in data streams
Jelani Nelson and David P. Woodruff · 2010
Later among the works it cites.
Fast approximation of matrix coherence and statistical leverage
Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, and David P. Woodruff · 2011
Later among the works it cites.
Faster least squares approximation
Petros Drineas, Michael W. Mahoney, S. Muthukrishnan, and Tamás Sarlós · 2011
Later among the works it cites.
Fast moment estimation in data streams in optimal space
Daniel M. Kane, Jelani Nelson, Ely Porat, and David P. Woodruff · 2011
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan · 2006
Cited alongside, same era.
Subspace sampling and relative-error matrix approximation: Column-row-based methods
Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan · 2006
Cited alongside, same era.
Improved approximation algorithms for large matrices via random projections
Tamás Sarlós · 2006
Cited alongside, same era.
Fast computation of low-rank matrix approximations
Dimitris Achlioptas and Frank McSherry · 2007
Cited alongside, same era.
Sampling from large matrices: An approach through geometric functional analysis
Mark Rudelson and Roman Vershynin · 2007
Cited alongside, same era.
The spectral method for general mixture models
Ravindran Kannan, Hadi Salmasian, and Santosh Vempala · 2008
Cited alongside, same era.
Linear and nonlinear programming
D.G. Luenberger and Y. Ye · 2008
Cited alongside, same era.
Avner Magen and Anastasios Zouzias · 2011
Later among the works it cites.
LSRN: A Parallel Iterative Solver for Strongly Over- or Under-Determined Systems
X. Meng, M. A. Saunders, and M. W. Mahoney · 2011
Later among the works it cites.
A matrix hyperbolic cosine algorithm and applications
Anastasios Zouzias · 2011
Later among the works it cites.
Improved matrix algorithms via the Subsampled Randomized Hadamard Transform
C. Boutsidis and A. Gittens · 2012
Closest in time.
Fast matrix rank algorithms and applications
Ho Yee Cheung, Tsz Chiu Kwok, and Lap Chi Lau · 2012
Closest in time.
Fast approximation of matrix coherence and statistical leverage
Petros Drineas, Michael Mahoney, Malik Magdon-Ismail, and David P. Woodruff · 2012
Closest in time.
Sparser Johnson-Lindenstrauss transforms
Daniel M. Kane and Jelani Nelson · 2012
Closest in time.
Low-distortion Subspace Embeddings in Input-sparsity Time and Applications to Robust Linear Regression
X. Meng and M. W. Mahoney · 2012
Closest in time.
Iterative 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. Nguyen · 2012
Closest in time.
Random projections for support vector machines
Saurabh Paul, Christos Boutsidis, Malik Magdon-Ismail, and Petros Drineas · 2012
Closest in time.
Randomized extended Kaczmarz for solving least-squares
Anastasios Zouzias and Nikolaos M. Freris · 2012
Closest in time.
The fast Cauchy transform and faster robust linear regression
K. Clarkson, P. Drineas, Malik Magdon-Ismail, M. Mahoney, Xiangrui Meng, and David P. Woodruff · 2013
Closest in time.