OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings

By Jelani Nelson, Huy L. Nguyen. IEEE Annual Symposium on Foundations of Computer Science, 2012

417 citations recorded by the source corpus.

An oblivious subspace embedding (OSE) given some parameters ε, d is a distribution D over matrices Π ∈ Rm×n such that for any linear subspace W ⊆ Rn with dim(W) = d, PΠ~D(∀x ∈ W ||Πx||2 ∈ (1 ± ε)||x||2) > 2/3. We show that a certain class of distributions, Oblivious Sparse Norm-Approximating Projections (OSNAPs), provides OSE's with m = O(d1+γ/ε2), and where every matrix Π in the support of the OSE has only s = Oγ(1/ε) non-zero entries per column, for γ > 0 any desired constant. Plugging OSNAPs into known algorithms for approximate least squares regression, ℓp regression, low rank approximation, and approximating leverage scores implies faster algorithms for all these problems. Our main result is essentially a Bai-Yin type theorem in random matrix theory and is likely to be of independent interest: we show that for any fixed U ∈ Rn×d with orthonormal columns and random sparse Π, all singular values of ΠU lie in [1 - ε, 1 + ε] with good probability. This can be seen as a generalization of the sparse Johnson-Lindenstrauss lemma, which was concerned with d = 1. Our methods also recover a slightly sharper version of a main result of [Clarkson-Woodruff, STOC 2013], with a much simpler proof. That is, we show that OSNAPs give an OSE with m = O(d2/ε2), s = 1.

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

View Paper: https://www.semanticscholar.org/paper/1e177a3f6417e7702750793dad70ad9e243cb58a

How researchers see this paper

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

In Computational Mathematics

In Computational Mechanics

In Computational Theory and Mathematics

Citations in the corpus

Sketching as a Tool for Numerical Linear Algebra (2014, methodology): “ntries of the matrix A. We call such algorithms input-sparsity algorithms, as they exploit the number of non-zero entries of A. The poly(d/ε) factors were subsequently optimized in a number of papers [92, 97, 18], leading to optimal algorithms even when nnz(A) is not too much larger than d. In paral”
GIANT: Globally Improved Approximate Newton Method for Distributed Optimization (2017, background): “ons of the rows of A. Popular random projections include, among many others, Gaussian projection [13], subsampled randomized Hadamard transform [8,21,49], Rademacher random variables [1], CountSketch [3,28,30]. 13 The quadratic function ˚. Let A tbe deﬁned in (4). We deﬁne the auxiliary function ˚ t”
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 nd use that to compute an estimate of the top eigenvector [18, 19, 20, 21, 22, 23].”
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].”
Optimal principal component analysis in distributed and streaming models (2015, background): “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 .”
Weighted low rank approximations with provable guarantees (2016, methodology): “In the latter case, much more efficient algorithms are known, and it is possible to compute such an Â in nnz(A) + n · poly(k/ ) time, where nnz(A) denotes the number of non-zero entries of A [16, 42, 44].”
Randomized numerical linear algebra: Foundations and algorithms (2020, background): “For randomized linear algebra applications, sparse embeddings were promoted in the papers (Clarkson and Woodruff 2013, Meng and Mahoney 2013, Nelson and Nguyen 2013, Urano 2013).”
Subspace Embeddings for the Polynomial Kernel (2014, background): “Nelson and Nguyen [13] showed that COUNTSKETCH still provides a subspace embedding if the entries are chosen from a 4-wise independent distribution.”
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation (2014, background): “R an OSNAP sparse subspace embedding matrix [41].”
Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization (2015, methodology): “For comparison, Table 1 includes Moore-Penrose pseudoinversion – computed via naive matrix multiplication and inversion routines, as well as by their asymptotically fastest counterparts – in order to compute a closed-form solution via the standard normal equations.”
Improved Distributed Principal Component Analysis (2014, methodology): “The recent fast sparse subspace embeddings [5] and its optimizations [17, 19] are particularly suitable for large scale sparse data sets, since their running time is linear in the number of non-zero entries in the data matrix, and they also preserve the sparsity of the data.”
Path Finding Methods for Linear Programming: Solving Linear Programs in Õ(vrank) Iterations and Faster Algorithms for Maximum Flow (2014, methodology): “Using [27], [22] to solve the linear systems, we obtain an algorithm that solves (1) in time”
Low rank approximation with entrywise l1-norm error (2017, methodology): “For least squares regression, a sequence of work [11, 24, 27, 60, 68, 71, 81] shows how to achieve algorithms running in nnz(A) + poly(d ) time.”
Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time (2023, background): “Definition G.16 (Sparse embedding matrix I (Nelson & Nguyên, 2013)) .”
Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence (2015, methodology): “Here we describe a construction given by [25, 19].”
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.”
Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression (2012, background): “Nelson and Nguyen also let us know that, at about the same time and using the same technique, but independent of us, they first published the O(d(2)/ (2)) embedding result [26].”
Low-Rank Approximation and Regression in Input Sparsity Time (2012, background): “Nelson and Nguyen [2012] obtained similar results for regression, and showed that sparse embeddings can embed into dimension O ( d 2 /ε 2 ) in O ( nnz ( A )) time.”