Tighter Low-rank Approximation via Sampling the Leveraged Element

Srinadh Bhojanapalli, Prateek Jain, Sujay Sanghavi

TL;DR

This paper introduces LELA (Leveraged Element Low-rank Approximation), a randomized algorithm that achieves high-accuracy (spectral norm) low-rank matrix approximations in "input sparsity" time. By combining biased entry-wise sampling with weighted alternating minimization, the authors bridge the gap between fast-but-loose Frobenius norm methods and slow-but-accurate spectral norm methods.

What Problem Does This Paper Address?

Low-rank approximation—finding a simpler, lower-dimensional version of a massive matrix—is a cornerstone of machine learning and data science (think PCA or recommendation systems). However, as datasets have grown to millions of rows and columns, traditional methods like Singular Value Decomposition (SVD) have become computationally prohibitive.

Existing randomized shortcuts usually fall into two camps:

  1. Fast but Weak: Algorithms that run in time proportional to the number of non-zero entries ($nnz(M)$) but only guarantee accuracy in the Frobenius norm (an average-case error metric).
  2. Slow but Strong: Algorithms that provide accuracy in the spectral norm (a worst-case error metric) but require $O(n^2)$ time, which is too slow for sparse, high-dimensional data.

The authors aim to provide the "best of both worlds": an algorithm that handles sparse inputs efficiently while delivering the tighter error guarantees of the spectral norm.

Methods

The proposed algorithm, LELA, operates in two distinct stages:

  1. Biased Entry-wise Sampling: Instead of sampling entire rows or columns, LELA samples individual entries. The sampling is "biased" using a hybrid distribution. It looks at the leverage scores (approximated by row and column norms) to find important structural elements and includes an $L_1$ term to ensure that high-magnitude "outlier" entries aren't missed. This step requires only two passes over the data.
  2. Weighted Alternating Minimization (WAltMin): After sampling a small subset of entries, the algorithm doesn't just fill the rest with zeros and run an SVD (the standard approach). Instead, it treats the problem like matrix completion. It searches for a low-rank factored form ($UV^T$) that minimizes the weighted squared error only on the sampled entries. By alternating between optimizing $U$ and $V$, the algorithm converges to a tight approximation.

The authors also extend this framework to two other major problems:

  • Direct Matrix Product Approximation: Approximating the low-rank structure of $AB$ without ever fully computing the product.
  • Distributed PCA: A version of the algorithm designed for settings where data is split across multiple servers, significantly reducing the amount of data that needs to be communicated between them.

Datasets

The paper evaluates the algorithm using synthetic datasets:

  • Random Matrices: $1000 \times 1000$ matrices with rank 5.
  • Power-law Matrices: Used to generate "coherent" matrices (where information is concentrated in a few entries) to test the robustness of the sampling strategy.
  • Noisy Matrices: Matrices where a low-rank signal is buried under Gaussian noise.

Note: No real-world benchmark datasets (like MovieLens or ImageNet) are discussed in the provided text.

Key Insights and Ideas

  • The Power of Weights: Standard sampling methods often suffer if the matrix is "coherent" (not uniform). By using weighted alternating minimization, the algorithm gives more importance to entries that were less likely to be sampled, effectively "balancing" the biased view of the data.
  • Beyond Incoherence: Most matrix completion literature assumes "incoherence" (that the matrix's information is spread out). LELA's sampling strategy is specifically designed to handle "coherent" matrices by using leverage scores to hunt down the concentrated information.
  • Spectral is Better: Most practitioners settle for Frobenius norm bounds because they are easier to prove. This paper shows that by changing the optimization objective from "SVD on a zero-filled matrix" to "AltMin on sampled entries," you can naturally achieve spectral norm bounds.

Key Results

  • Computational Efficiency: LELA runs in $O(nnz(M) + \frac{n \kappa^2 r^5}{\epsilon^2})$ time. For sparse matrices, the $nnz(M)$ term dominates, making it much faster than $O(n^2)$ methods.
  • Accuracy: The algorithm provides a spectral norm guarantee: $\|M - \widehat{M}_r\| \le \|M - M_r\| + \epsilon \|M - M_r\|_F$. This is significantly tighter than the standard relative-error Frobenius bounds.
  • Simulation Performance: In tests on "coherent" matrices, LELA significantly outperformed traditional Random Projection methods. While Random Projection's error remained high even with many samples, LELA's error dropped sharply as more "leveraged" elements were sampled.
  • Communication: In the distributed PCA setting, LELA achieves communication complexity that scales linearly with the number of features ($d$) and the number of servers ($s$), making it highly scalable.

Limitations and Future Work

  • Condition Number Dependence: The algorithm's complexity depends quadratically on the condition number $\kappa = \sigma_1/\sigma_r$. If a matrix has a very "flat" singular value spectrum (where the first and $r$-th singular values are nearly equal), the algorithm is highly efficient. However, if $\kappa$ is very large, the number of required samples increases.
  • Theoretical Gap: The authors note that while their analysis requires $O(\kappa^2)$, recent advances in matrix completion suggest this might be improvable to $O(\log \kappa)$. They leave this tighter theoretical analysis for future research.
  • Parameter Tuning: The algorithm requires setting the number of iterations $T$ and the number of samples $m$, which may require some trial and error in practical applications.

Summary updated

Abstract

In this work, we propose a new randomized algorithm for computing a low-rank approximation to a given matrix. Taking an approach different from existing literature, our method first involves a specific biased sampling, with an element being chosen based on the leverage scores of its row and column, and then involves weighted alternating minimization over the factored form of the intended low-rank matrix, to minimize error only on these samples. Our method can leverage input sparsity, yet produce approximations in {\em spectral} (as opposed to the weaker Frobenius) norm; this combines the best aspects of otherwise disparate current results, but with a dependence on the condition number $\kappa = \sigma_1/\sigma_r$. In particular we require $O(nnz(M) + \frac{n\kappa^2 r^5}{\epsilon^2})$ computations to generate a rank-$r$ approximation to $M$ in spectral norm. In contrast, the best existing method requires $O(nnz(M)+ \frac{nr^2}{\epsilon^4})$ time to compute an approximation in Frobenius norm. Besides the tightness in spectral norm, we have a better dependence on the error $\epsilon$. Our method is naturally and highly parallelizable. Our new approach enables two extensions that are interesting on their own. The first is a new method to directly compute a low-rank approximation (in efficient factored form) to the product of two given matrices; it computes a small random set of entries of the product, and then executes weighted alternating minimization (as before) on these. The sampling strategy is different because now we cannot access leverage scores of the product matrix (but instead have to work with input matrices). The second extension is an improved algorithm with smaller communication complexity for the distributed PCA setting (where each server has small set of rows of the matrix, and want to compute low rank approximation with small amount of communication with other servers).
BibTeX
@inproceedings{bhojanapalli2015tighter,
  author = {Srinadh Bhojanapalli and Prateek Jain and Sujay Sanghavi},
  title = {{Tighter Low-rank Approximation via Sampling the Leveraged Element}},
  booktitle = {SODA},
  year = {2015},
  url = {https://openreview.net/forum?id=feajxJB2F7c},
}
Figure