Numerical linear algebra in the streaming model

By Kenneth L. Clarkson, David P. Woodruff. Symposium on the Theory of Computing, 2009

403 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/6d8d4423d990d9398fcec42f0811bf8d81528592

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computational Theory and Mathematics

Citations in the corpus

Memory Limited, Streaming PCA (2013, background): “Indeed, it is straightforward to check that the guarantees presented in ([5, 8]) are not strong enough to guarantee recovery of the spike.”
Low rank approximation with entrywise l1-norm error (2017, background): “1 in [23] and relating entrywise `1-norm to Frobenius norm.”
Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm (2016, methodology): “Most of the existing methods here first compute a sketch of the matrix and use that to compute an estimate of the top eigenvector [18, 19, 20, 21, 22, 23].”
Low-Rank Approximation and Regression in Input Sparsity Time (2012, methodology): “This section gives algorithms for low-rank approximation, understood using generalized regression analysis, as in earlier work suchas Sarl´os [2006] and Clarkson and Woodruff [2009].”
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation (2014, background): “Additionally, the same matrix family except with elements only O(log(k/δ))-independent [14].”
Faster least squares approximation (2007, background): “Third, very recently, Clarkson and Woodruff proved space lower bounds on related problems [6], and Nguyen, Do, and Tran achieved a small improvement in the sampling complexity for related problems [14].”
Finding and Leveraging Structure in Learning Problems (2012, background): “Several fast algorithms are known for (approximately) minimizing least squares that have different computational complexities: those based on sketching [Clarkson and Woodruff, 2009], principal component regression [Jolliffe, 1982], gradient descent.”
Stat260/cs294: Randomized Algorithms for Matrices and Data (methodology): “…Approximation " • Achlioptas, " Database-friendly random projections: Johnson-Lindenstrauss with binary coins " 5.1 Spectral norm bounds for matrix multiplication Here, we will provide a spectral norm bound for the error of the approximation constructed by the BasicMatrixMultiplication algorithm.”
Randomized Extended Kaczmarz for Solving Least Squares (2012, methodology): “…generic two step procedure: ﬁrst randomly (and efﬁciently) project the linear system into sufﬁciently many dimensions, and second return the solution of the down-sampled linear system as an approximation to the original optimal solution [DMM06, Sar06, CW09, NDT09, MZ11, DMMS11], see also [CW12].”
Communication Complexity of Distributed Convex Learning and Optimization (2015, background): “In the context of lower bounds for one-round algorithms, the results of [6] imply that Ω(d(2)) bits of communication are required to solve linear regression in one round of communication.”
A unified framework for approximating and clustering data (2011, methodology): “Some small space streaming algorithms are available in the turnstile model (where the points are constrained to be on an inte-ger grid of size n O (1) ) for l z regression where 1 ≤ z ≤ 2 by [24] and [13] for z = 2 .”
A Randomized Algorithm for Principal Component Analysis (2008, methodology): “acceptable. Now, pivoted QR-decomposition algorithms are not the only algorithms which can compute a rank-k approximation using O(nmk) ﬂops. However, other algorithms, such as those of [1], [2], [3], [5], [7], [8], [10], [11], [12], [13], [14], [15], [16], [17], [18], [21], [22], [23], [24], [25], [”
Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension (2019, methodology): “Designing small-space algorithms for estimating Schatten norms of an input matrix in the data-stream model was investigated recently for various matrix classes and stream types (Clarkson and Woodruff, 2009; Andoni and Nguyen, 2013; Li et al., 2014; Li and Woodruff, 2016a;b; 2017; Braverman et al., 2”
Optimal principal component analysis in distributed and streaming models (2015, methodology): “(Dense Johnson-Lindenstrauss matrix ) [part of Theorem 12 in [20]] For ε 1 , suppose each entry of W ∈ R n × ξ is chosen O ( k ) -wise independently and uniformly in { 1 / √ ξ, − 1 / √ ξ } where ξ = O ( kε − 2 ) [17].”
Online sketching hashing (2015, background): “Our work is largely inspired by the idea of “data sketching” [21, 18].”
Graph sketches: sparsification, spanners, and subgraphs (2012, background): “, finding heavy hitters and quantiles [10, 13]; estimating norms and support sizes [32, 33]; and constructing histograms and low-dimensional approximations [11, 26].”
Subspace Embeddings for the Polynomial Kernel (2014, background): “2 of Clarkson and Woodruff [4], which is in turn based on Theorem 3.”