Fetching the paper…
Reading the bibliography…
This survey highlights the recent advances in algorithms for numerical linear algebra that have come from the technique of linear sketching, whereby given a matrix, one first compresses it to a much smaller matrix by multiplying it by a (usually) random matrix with certain properties.
On the Area of Convex Curves with Conjugate Diameters
H. Auerbach · 1930
Earlier work this paper cites.
Finite dimensional subspaces of l p l_{p}
D. Lewis · 1978
Earlier work this paper cites.
The best constants in the khintchine inequality
Uffe Haagerup · 1981
Earlier work this paper cites.
More on embedding subspaces of l p l_{p} into ℓ r n \ell_{r}^{n}
Schechtman · 1987
Earlier work this paper cites.
Approximation of zonoids by zonotopes
J. Bourgain, J. Lindenstrauss, and V. Milman · 1989
Earlier work this paper cites.
Uncertainty principles and signal recovery
D. Donoho and P. Stark · 1989
Earlier work this paper cites.
Embedding subspaces of l 1 l_{1} into ℓ 1 n \ell_{1}^{n}
Michel Talagrand · 1990
Earlier work this paper cites.
Limit of the smallest eigenvalue of a large dimensional sample covariance matrix
Z. Bai and Y.Q. Yin · 1993
Earlier work this paper cites.
Matrix computations (3. ed.)
Gene H. Golub and Charles F. van Loan · 1996
Earlier work this paper cites.
Mosaic-skeleton approximations
E. Tyrtyshnikov · 1996
Earlier work this paper cites.
A theory of pseudoskeleton approximations
S.A. Goreinov, EE Tyrtyshnikov, and NL Zamarashkin · 1997
Earlier work this paper cites.
Pseudo-skeleton approximations by matrices of maximal volume
S.A. Goreinov, N.L. Zamarashkin, and E.E. Tyrtyshnikov · 1997
Earlier work this paper cites.
Improved bound for rank revealing LU factorizations
T.M. Hwang, W.W. Lin, and D. Pierce · 1997
Earlier work this paper cites.
Communication Complexity
E. Kushilevitz and N. Nisan · 1997
Earlier work this paper cites.
Arbitrary-norm separating plane
O. L. Mangasarian · 1997
Earlier work this paper cites.
Approximate nearest neighbors: towards removing the curse of dimensionality
P. Indyk and R. Motwani · 1998
Earlier work this paper cites.
On data structures and asymmetric communication complexity
Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson · 1998
Earlier work this paper cites.
Four algorithms for the efficient computation of truncated QR approximations to a sparse matrix
G.W. Stewart · 1999
Earlier work this paper cites.
Adaptive estimation of a quadratic functional by model selection
Béatrice Laurent and Pascal Massart · 2000
Earlier work this paper cites.
On the existence and computation of rank-revealing LU factorizations
C.T. Pan · 2000
Earlier work this paper cites.
Incomplete cross approximation in the mosaic-skeleton method
E. Tyrtyshnikov · 2000
Earlier work this paper cites.
Algorithms for non-negative matrix factorization
Daniel D. Lee and H. Sebastian Seung · 2001
Earlier work this paper cites.
Nonparametric Goodness-of-Fit Testing Under Gaussian Models
Yuri Ingster and I. A. Suslina · 2002
Earlier work this paper cites.
Lectures on Discrete Geometry
Jiri Matousek · 2002
Earlier work this paper cites.
Database-friendly random projections: Johnson-lindenstrauss with binary coins
Dimitris Achlioptas · 2003
Earlier work this paper cites.
Latent dirichlet allocation
David M Blei, Andrew Y Ng, and Michael I Jordan · 2003
Earlier work this paper cites.
Pass efficient algorithms for approximating large matrices
P. Drineas and R. Kannan · 2003
Earlier work this paper cites.
Very tight embeddings of subspaces of l p l_{p} , 1 = p < 2 1=p<2 , into ℓ p n \ell_{p}^{n}
William Johnson and Gideon Schechtman · 2003
Earlier work this paper cites.
Robust subspace computation using ℓ 1 \ell_{1} norm, 2003
Q. Ke and T. Kanade · 2003
Earlier work this paper cites.
A bound on the deviation probability for sums of non-negative random variables
A. Maurer · 2003
Earlier work this paper cites.
A comparison of numerical optimizers for logistic regression
Thomas P. Minka · 2003
Earlier work this paper cites.
Strong rank revealing LU factorizations
L. Miranian and M. Gu · 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.
Strong rank revealing Cholesky factorization
M. Gu and L. Miranian · 2004
Earlier work this paper cites.
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
Daniel A. Spielman and Shang-Hua Teng · 2004
Earlier work this paper cites.
Fast Transforms Based on Structured Matrices With Applications to The Fast Multipole Method
Zhihui Tang · 2004
Earlier work this paper cites.
Algorithm 844: Computing sparse reduced-rank approximations to sparse matrices
Michael W Berry, Shakhina A Pulatova, and GW Stewart · 2005
Earlier work this paper cites.
Subgradient and sampling algorithms for ℓ 1 \ell_{1} regression
K. Clarkson · 2005
Earlier work this paper cites.
Spectral techniques applied to sparse random graphs
Uriel Feige and Eran Ofek · 2005
Earlier work this paper cites.
Robust l 1 {}_{\mbox{1}} norm factorization in the presence of outliers and missing data by alternative convex programming
Qifa Ke and Takeo Kanade · 2005
Earlier work this paper cites.
Data streams: algorithms and applications
S. Muthukrishnan · 2005
Earlier work this paper cites.
Approximate nearest neighbors and the fast johnson-lindenstrauss transform
Nir Ailon and Bernard Chazelle · 2006
Earlier work this paper cites.
A fast random sampling algorithm for sparsifying matrices
Sanjeev Arora, Elad Hazan, and Satyen Kale · 2006
Cited alongside, same era.
Matrix approximation and projective clustering via volume sampling
Amit Deshpande, Luis Rademacher, Santosh Vempala, and Grant Wang · 2006
Cited alongside, same era.
Fast Monte Carlo algorithms for matrices III: Computing a compressed approximate matrix decomposition
P. Drineas, R. Kannan, and M.W. Mahoney · 2006
Cited alongside, same era.
Subspace sampling and relative-error matrix approximation: Column-based methods
P. Drineas, M. W. Mahoney, and S. Muthukrishnan · 2006
Cited alongside, same era.
Subspace sampling and relative-error matrix approximation: Column-row-based methods
P. Drineas, M. W. Mahoney, and S. Muthukrishnan · 2006
Cited alongside, same era.
Sampling algorithms for ℓ 2 \ell_{2} regression and applications
Low Rank Matrix-valued Chernoff Bounds and Approximate Matrix Multiplication
A. Magen and A. Zouzias · 2011
Later among the works it cites.
Randomized algorithms for matrices and data
Michael W. Mahoney · 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.
Subspace embeddings for the l 1 {}_{\mbox{1}} -norm with applications
Christian Sohler and David P. Woodruff · 2011
Later among the works it cites.
Spectral sparsification of graphs
Daniel A. Spielman and Shang-Hua Teng · 2011
Later among the works it cites.
Improved analysis of the subsampled randomized hadamard transform
Joel Tropp · 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…
P. Drineas, M.W. Mahoney, and S. Muthukrishnan · 2006
Cited alongside, same era.
Subspace sampling and relative-error matrix approximation: Column-based methods
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.
Stable distributions, pseudorandom generators, embeddings, and data stream computation
Piotr Indyk · 2006
Cited alongside, same era.
Estimates of moments and tails of Gaussian chaoses
Rafał Latała · 2006
Cited alongside, same era.
Improved approximation algorithms for large matrices via random projections
T. Sarlós · 2006
Cited alongside, same era.
Sampling-based dimension reduction for subspace approximation
A. Deshpande and K. Varadarajan · 2007
Cited alongside, same era.
Introduction to the non-asymptotic analysis of random matrices
Roman Vershynin · 2011
Later among the works it cites.
High frequency moment via max stability
Alexandr Andoni · 2012
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 · 2012
Later among the works it cites.
Optimal column-based low-rank matrix reconstruction
Venkatesan Guruswami and Ali Kemal Sinop · 2012
Later among the works it cites.
Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation
Mikkel Thorup and Yin Zhang · 2012
Later among the works it cites.
On the sensitivity of shape fitting problems
Kasturi Varadarajan and Xin Xiao · 2012
Later among the works it cites.
A matrix hyperbolic cosine algorithm and applications
Anastasios Zouzias · 2012
Later among the works it cites.
Sketching structured matrices for faster nonlinear regression
Haim Avron, Vikas Sindhwani, and David P. Woodruff · 2013
Later among the works it cites.
Toward a unified theory of sparse dimensionality reduction in euclidean space
Jean Bourgain and Jelani Nelson · 2013
Later among the works it cites.
Near optimal column based matrix reconstruction
Christos Boutsidis, Petros Drineas, and Malik Magdon-Ismail · 2013
Later among the works it cites.
The fast cauchy transform and faster robust linear regression
Kenneth L. Clarkson, Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, Xiangrui Meng, and David P. Woodruff · 2013
Later among the works it cites.
Low rank approximation and regression in input sparsity time
Kenneth L Clarkson and David P Woodruff · 2013
Later among the works it cites.
Turning big data into tiny data: Constant-size coresets for k-means, pca and projective clustering
Dan Feldman, Melanie Schmidt, and Christian Sohler · 2013
Later among the works it cites.
Revisiting the nystrom method for improved large-scale machine learning
Alex Gittens and Michael W Mahoney · 2013
Later among the works it cites.
How robust are linear sketches to adaptive inputs?
Moritz Hardt and David P. Woodruff · 2013
Later among the works it cites.
Iterative row sampling
Mu Li, Gary L. Miller, and Richard Peng · 2013
Later among the works it cites.
Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
Xiangrui Meng and Michael W Mahoney · 2013
Later among the works it cites.
Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings
Jelani Nelson and Huy L Nguyên · 2013
Later among the works it cites.
Sparsity lower bounds for dimensionality reducing maps
Jelani Nelson and Huy L. Nguy e ^ ~ \tilde{\hat{\mbox{e}}} n · 2013
Later among the works it cites.
Personal communication, 2013
Huy Le Nguy e ^ ~ \tilde{\hat{\mbox{e}}} n · 2013
Later among the works it cites.
Improving cur matrix decomposition and the nystrom approximation via adaptive sampling
S. Wang and Z. Zhang · 2013
Later among the works it cites.
Subspace embeddings and ℓ p \ell_{p} -regression using exponential random variables
David P. Woodruff and Qin Zhang · 2013
Later among the works it cites.
Faster ridge regression via the subsampled randomized hadamard transform
Dean Foster Yichao Lu, Paramveer Dhillon and Lyle Ungar · 2013
Later among the works it cites.
Subspace embeddings for the polynomial kernel
Haim Avron, Huy L. Nguy e ^ ~ \tilde{\hat{\mbox{e}}} n, and David P. Woodruff · 2014
Closest in time.
Fast and communication efficient algorithms for distributd pca
Maria-Florina Balcan, Vandana Kanchanapally, Yingyu Liang, and David P. Woodruff · 2014
Closest in time.
Optimal cur matrix decompositions
Christos Boutsidis and David P. Woodruff · 2014
Closest in time.
Dimensionality reduction for k-means clustering and low rank approximation
Michael Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu · 2014
Closest in time.
Optimal approximate matrix product in terms of stable rank
Michael Cohen, Jelani Nelson, and David P. Woodruff · 2014
Closest in time.
Uniform sampling for matrix approximation
Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford · 2014
Closest in time.
Sparser johnson-lindenstrauss transforms
Daniel M. Kane and Jelani Nelson · 2014
Closest in time.
Principal component analysis and higher correlations for distributed data
Ravi Kannan, Santosh Vempala, and David P. Woodruff · 2014
Closest in time.
Single pass spectral sparsification in dynamic streams
Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford · 2014
Closest in time.
On sketching matrix norms and the top singular vector
Yi Li, Huy L. Nguy e ^ ~ \tilde{\hat{\mbox{e}}} n, and David P. Woodruff · 2014
Closest in time.
Lower bounds for oblivious subspace embeddings
Jelani Nelson and Huy L. Nguyên · 2014
Closest in time.
Personal communication, 2014
Oded Regev · 2014
Closest in time.
Low rank approximation lower bounds in row-update streams
David P. Woodruff · 2014
Closest in time.