Low-Rank Approximation and Regression in Input Sparsity Time

Kenneth L. Clarkson, David P. WoodruffJournal of the ACM 2017 · DOI

TL;DR

This paper introduces "sparse embedding matrices" that can approximate linear transformations of sparse matrices in time proportional to the number of non-zero entries, a significant improvement over previous methods. This breakthrough enables the fastest known algorithms for fundamental problems like least-squares regression and low-rank approximation, with running times that depend primarily on the sparsity of the input.

What Problem Does This Paper Address?

Many important problems in numerical linear algebra, such as finding the best approximate solution to $Ax=b$ (least-squares regression) or finding a lower-rank approximation of a matrix $A$ (low-rank approximation), can be solved much faster using randomized algorithms. A key component in many of these algorithms is a "subspace embedding," which is a matrix $S$ that, when multiplied by $A$, preserves the norms of vectors in the column space of $A$ (i.e., $||SAx|| \approx ||Ax||$). The challenge has been that existing subspace embeddings, while effective, required computational time that depended heavily on the dimensions of the matrix $A$ (e.g., $nd \log d$), making them slow for large, sparse matrices where the number of non-zero entries ($nnz(A)$) is much smaller than $nd$. This paper aims to bridge this gap by developing subspace embeddings that can be computed and applied much more efficiently, specifically in time proportional to $nnz(A)$.

Methods

The core innovation is the introduction of "sparse embedding matrices." These are random matrices $S$ designed such that $SA$ can be computed in $O(nnz(A))$ time. The construction of $S$ involves a random mapping of indices and a sparse matrix structure, inspired by techniques like CountSketch. The key insight is that by carefully analyzing the structure of vectors within the column space of $A$, these sparse matrices can still provide the necessary norm preservation property ($||SAx|| \approx ||Ax||$) with high probability.

Once these efficient sparse embedding matrices are developed, the paper shows how to plug them into existing frameworks for solving various linear algebra problems. This includes:

  • Least-Squares Regression: Finding a vector $x'$ that minimizes $||Ax' - b||_p$ for $p=2$ (Euclidean norm) or more generally for $p \in [1, \infty)$.
  • Low-Rank Approximation: Finding a matrix $A_k$ of rank $k$ that is close to $A$ in Frobenius norm ($||A - A_k||_F$).
  • Leverage Score Approximation: Estimating the importance of individual rows of $A$.

The paper presents several algorithms for these problems, leveraging the sparse embedding matrices to achieve significant speedups, particularly when the input matrix $A$ is sparse.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithms and their performance guarantees, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Sparse Embeddings for Efficiency: The most significant insight is the creation of subspace embeddings that can be applied in $O(nnz(A))$ time. This is a major departure from previous methods that had dependencies on $nd$ or $d^2$, unlocking faster algorithms for sparse data.
  • Leverage Scores as a Key Tool: The paper highlights the importance of leverage scores, which measure the "importance" of rows in a matrix. Understanding and approximating these scores is crucial for developing efficient algorithms.
  • "Heavy" vs. "Light" Coordinates: The analysis of the sparse embedding matrices relies on partitioning the coordinates of vectors into "heavy" (large leverage scores) and "light" (small leverage scores) sets. This allows for a more refined analysis and optimization of the embedding process.
  • Bridging Theory and Practice: The paper demonstrates how theoretical advancements in subspace embeddings can lead to practical improvements in solving fundamental linear algebra problems, with potential implications for machine learning and data analysis.

Key Results

The paper presents several algorithms with improved time complexities:

  • Least-Squares Regression: Achieves $O(nnz(A)) + \tilde{O}(d^3 \epsilon^{-2})$ time for Euclidean regression, and $O(nnz(A) \log n) + O(r \epsilon^{-1})$ time for $l_p$-regression.
  • Low-Rank Approximation: Achieves $O(nnz(A)) + \tilde{O}(nk^2 \epsilon^{-4} + k^3 \epsilon^{-5})$ time for finding a rank-$k$ approximation.
  • Leverage Score Approximation: Achieves $O(nnz(A) \log n) + O(r^3)$ time for approximating all leverage scores.

These results represent significant improvements, especially for sparse matrices, by making the $nnz(A)$ term dominant.

Limitations and Future Work

  • Additive Terms: While the dependence on $nnz(A)$ is optimized, the "additive terms" in the running times (e.g., $d^3 \epsilon^{-2}$ or $k^3 \epsilon^{-5}$) can still be significant if $d$ or $k$ are large. The paper discusses methods to optimize these terms further.
  • Constant Factors: The theoretical guarantees often come with large constant factors, which might affect practical performance for smaller problem sizes. The authors mention preliminary experimental results suggesting their algorithms are of interest in practice.
  • Generalization: The paper focuses on specific problems, and future work could explore applying these sparse embedding techniques to a wider range of numerical linear algebra tasks.
  • Experimental Validation: While preliminary experiments are mentioned, more extensive empirical studies would be valuable to demonstrate the practical advantages of these new algorithms.

Summary updated

Abstract

We design a new distribution over m × n matrices S so that, for any fixed n × d matrix A of rank r , with probability at least 9/10, ∥ SAx ∥ 2 = (1 ± ε)∥ Ax ∥ 2 simultaneously for all x ∈ R d . Here, m is bounded by a polynomial in r ε − 1 , and the parameter ε ∈ (0, 1]. Such a matrix S is called a subspace embedding . Furthermore, SA can be computed in O (nnz( A )) time, where nnz( A ) is the number of nonzero entries of A . This improves over all previous subspace embeddings, for which computing SA required at least Ω( nd log d ) time. We call these S sparse embedding matrices . Using our sparse embedding matrices, we obtain the fastest known algorithms for overconstrained least-squares regression, low-rank approximation, approximating all leverage scores, and ℓ p regression. More specifically, let b be an n × 1 vector, ε > 0 a small enough value, and integers k , p ⩾ 1. Our results include the following. — Regression: The regression problem is to find d × 1 vector x ′ for which ∥ Ax ′ − b ∥ p ⩽ (1 + ε)min x ∥ Ax − b ∥ p . For the Euclidean case p = 2, we obtain an algorithm running in O (nnz( A )) + Õ ( d 3 ε −2 ) time, and another in O (nnz( A )log(1/ε)) + Õ ( d 3 log (1/ε)) time. (Here, Õ ( f ) = f ċ log O (1) ( f ).) For p ∈ [1, ∞), more generally, we obtain an algorithm running in O (nnz( A ) log n ) + O ( r \ε −1 ) C time, for a fixed C . — Low-rank approximation: We give an algorithm to obtain a rank- k matrix  k such that ∥ A −  k ∥ F ≤ (1 + ε )∥ A − A k ∥ F , where A k is the best rank- k approximation to A . (That is, A k is the output of principal components analysis, produced by a truncated singular value decomposition, useful for latent semantic indexing and many other statistical problems.) Our algorithm runs in O (nnz( A )) + Õ ( nk 2 ε −4 + k 3 ε
BibTeX
@article{clarkson2017low,
  author = {Kenneth L. Clarkson and David P. Woodruff},
  title = {{Low-Rank Approximation and Regression in Input Sparsity Time}},
  journal = {Journal of the ACM},
  year = {2017},
  doi = {10.1145/3019134},
}
Figure