Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression

By Xiangrui Meng, Michael W. Mahoney. Symposium on the Theory of Computing, 2012

298 citations recorded by the source corpus.

Low-distortion embeddings are critical building blocks for developing random sampling and random projection algorithms for common linear algebra problems. We show that, given a matrix A ∈ R^{n x d} with n >> d and a p ∈ [1, 2), with a constant probability, we can construct a low-distortion embedding matrix Π ∈ R^{O(poly(d)) x n} that embeds A_p, the l_p subspace spanned by A's columns, into (R^O(poly(d)), |~cdot~|_p); the distortion of our embeddings is only O(poly(d)), and we can compute Π A in O(nnz(A)) time, i.e., input-sparsity time. Our result generalizes the input-sparsity time l₂ subspace embedding by Clarkson and Woodruff [STOC'13]; and for completeness, we present a simpler and improved analysis of their construction for l₂. These input-sparsity time l_p embeddings are optimal, up to constants, in terms of their running time; and the improved running time propagates to applications such as (1 pm ε)-distortion l_p subspace embedding and relative-error l_p regression. For l₂, we show that a (1+ε)-approximate solution to the l₂ regression problem specified by the matrix A and a vector b ∈ Rⁿ can be computed in O(nnz(A) + d³ log(d/ε) /ε^2) time; and for l_p, via a subspace-preserving sampling procedure, we show that a (1 pm ε)-distortion embedding of A_p into R^O(poly(d)) can be computed in O(nnz(A) ⋅ log n) time, and we also show that a (1+ε)-approximate solution to the l_p regression problem min_{x ∈ R^d} |A x - b|_p can be computed in O(nnz(A) ⋅ log n + poly(d) log(1/ε)/ε²) time. Moreover, we can also improve the embedding dimension or equivalently the sample size to O(d^3+p/2 log(1/ε) / ε²) without increasing the complexity.

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

View Paper: https://www.semanticscholar.org/paper/7d5293f1053748bd8b93f5b269f8dcc59c1132fb

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

1. David P. Woodruff
2. Michael W. Mahoney
3. Shusen Wang
4. Peilin Zhong
5. Joel A. Tropp
6. Christopher R'e
7. Zhao Song
8. Farbod Roosta-Khorasani

In Computational Mechanics

1. David P. Woodruff
2. Michael W. Mahoney
3. Shusen Wang
4. Joel A. Tropp
5. Zhao Song
6. Peilin Zhong
7. Farbod Roosta-Khorasani
8. Kenneth L. Clarkson

In Computational Theory and Mathematics

1. David P. Woodruff
2. Michael W. Mahoney
3. Kenneth L. Clarkson
4. Per-Gunnar Martinsson
5. Peilin Zhong
6. Zhao Song
7. Shusen Wang
8. Joel A. Tropp

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”
• Low-Rank Approximation and Regression in Input Sparsity Time (2012, methodology): “Meng and Mahoney [2012] improved on the first version of our additive terms for subspace embeddings, and showed that these ideas can also be applied to (cid:4) p regression, for 1 ≤ p < 2; our work on this in Section 9 achieves 1 ≤ p < ∞ , and was done independently.”
• 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).”
• Handbook of Big Data (2016, methodology): “The software will be available as an R-package, but the instructions below do not reflect this and get the reader going by sourcing the software from the first author’s site.”
• 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].”
• 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 ).”
• Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition (2015, background): “Recent work on sparse Johnson-Lindenstrauss type matrices [6, 38, 39] has significantly reduced the cost of multiplying AΠ, bringing the cost of Frobenius error low-rank approximation down toO(nnz(A)+ npoly(k/ )) time, where the first term is considered to dominate since typically k n, d.”
• Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time (2023, methodology): “This approach was generalized by using p -stable random variables in work of Meng and Mahoney (Meng & Mahoney, 2013) to ℓ p -norms when 1 p 2 , where they showed there exist ℓ p oblivious subspace embeddings with O ( d log d ) rows and κ = O (( d log d ) 1 /p ) .”
• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation (2014, background): “Additionally, the same matrix family with position and sign determined by a 4-independent hash function [15, 39, 41].”
• Improved Distributed Principal Component Analysis (2014, methodology): “(Clarkson and Woodruff, 2013; Meng and Mahoney, 2013; Nelson and Nguyên, 2012) Suppose n > d and ` = O(d 2 2 ).”
• 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].”
• 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 .”
• GIANT: Globally Improved Approximate Newton Method for Distributed Optimization (2017, background): “…others, Gaussian projection (Johnson and Lindenstrauss, 1984), subsampled randomized Hadamard transform (Drineas et al., 2011, Lu et al., 2013, Tropp, 2011), Rademacher random variables (Achlioptas, 2003), CountSketch (Clarkson and Woodruff, 2013, Meng and Mahoney, 2013, Nelson and Nguyˆen, 2013).”