Low-Rank Approximation and Regression in Input Sparsity Time

By Kenneth L. Clarkson, David P. Woodruff. arXiv.org, 2012

732 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

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

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 Numerical Analysis

Citations in the corpus

Dimensionality Reduction for k-Means Clustering and Low Rank Approximation (2014, methodology): “They relax the guarantee of subspace embeddings, which have received significant attention recently [43, 15].”
Handbook of Big Data (2016, methodology): “The software will be available as an R-package, but the instructions below do not reﬂect this and get the reader going by sourcing the software from the ﬁrst author’s site.”
Weighted low rank approximations with provable guarantees (2016, methodology): “This also generalizes affine embeddings in [16] in which t = 1 and B1 may have multiple columns; we stress that the design matrices A may be different.”
Optimal principal component analysis in distributed and streaming models (2015, methodology): “One could hope to do for communication what recent work on input sparsity algorithms [18, 35, 36, 12, 21] has done for computation, i.e., obtain protocols sensitive to the number of non-zero entries of A .”
Improved Distributed Principal Component Analysis (2014, methodology): “(Clarkson and Woodruff, 2013; Meng and Mahoney, 2013; Nelson and Nguyên, 2012) Suppose n > d and ` = O(d 2 2 ).”
Sketching as a Tool for Numerical Linear Algebra (2014, background): “Suppose r = Θ(d/ε2) and S is a r × n matrix of i.i.d. normal random variables with mean zero and variance 1/r, denoted N(0, 1/r).”
A statistical perspective on algorithmic leveraging (2013, unknown): “, least-squares approximation [11, 12], least absolute deviations regression [6, 29], and low-rank matrix approximation [28, 7].”
Simple and deterministic matrix sketching (2012, background): “A recent result along these lines [8], gives simple and efficient subspace embeddings that can be applied in time O(nnz(A)) for any matrix A.”
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].”
Dictionary learning for integrative, multimodal, and massively scalable single-cell analysis (2022, unknown): “Here, we perform sketching using a leverage score sampling-based strategy that has been proposed for large-scale information retrieval problems 56 and can be rapidly and efficiently computed on sparse datasets.”
Subspace Embeddings for the Polynomial Kernel (2014, methodology): “Sketching has emerged as a powerful dimensionality reduction technique for accelerating statistical learning techniques such as `p-regression, low rank approximation, and principal component analysis (PCA) [12, 5, 14].”
OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings (2012, methodology): “We furthermore point out that another reduction from (1 + ε)-approximate least squares regression to OSE’s via preconditioning followed by gradient descent actually only needs an OSE with constant distortion independent of ε (see [11]), so that ε = Θ(1) in an OSE is of primary interest.”
Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition (2015, methodology): “1 Prior Work The fastest randomized SVD algorithms [3, 5] run in O(nnz(A)) time1, are based on non-iterative sketching methods, and return a rank k matrix Z with orthonormal columns z1, .”
Low rank approximation with entrywise l1-norm error (2017, methodology): “To improve the approximation factor, after computing SA, we `1-project each of the rows of A onto SA using linear programming or fast algorithms for `1-regression [24, 68], obtaining an n × d matrix B of rank O (k logk ).”
Solving linear programs in the current matrix multiplication time (2018, result): “Similar to (2), Lemma 4.2 shows that The previously fastest algorithm involves maintaining the matrix inverse ( A A (cid:62) ) − 1 using sub-space embedding techniques [Sar06, CW13, NN13] and leverage score sampling [SS11].”