A Randomized Algorithm for Principal Component Analysis.

Vladimir Rokhlin, Arthur Szlam, Mark TygertSIAM J. Matrix Analysis Applications 2009 · OpenReview

TL;DR

This paper introduces a novel randomized algorithm for Principal Component Analysis (PCA) that efficiently computes highly accurate low-rank approximations of matrices, even for very large datasets. Unlike previous methods that struggled with accuracy on large matrices with slowly decaying singular values, this algorithm achieves near-optimal accuracy with high probability.

What Problem Does This Paper Address?

Principal Component Analysis (PCA) is a cornerstone technique in data analysis, machine learning, and data mining. At its core, PCA involves finding a low-rank approximation of a data matrix. The "best" low-rank approximation is typically defined by the Singular Value Decomposition (SVD). However, computing the full SVD for large matrices (e.g., millions of rows or columns) is computationally prohibitive. Existing efficient algorithms for low-rank approximation often sacrifice accuracy, especially when the data matrix has a "noisy" structure where singular values decay slowly. This means that for many real-world applications, these approximations are not good enough, leading to a trade-off between computational cost and the quality of the results. The paper aims to bridge this gap by providing an algorithm that is both efficient and delivers accuracy very close to the theoretical best possible, regardless of matrix size or singular value decay rate.

Methods

The paper proposes a randomized algorithm that leverages the power of random sampling to achieve high accuracy. The core idea is to apply the matrix (or its transpose) to carefully chosen random vectors. This process helps to identify the dominant components of the matrix without explicitly computing the full SVD.

The main algorithm (Subsection 4.1) involves five steps:

  1. Forming an intermediate matrix R: This involves multiplying the input matrix A (or its transpose) by a random matrix G and then by A or A^T A. This step is crucial for enhancing the decay of singular values.
  2. Computing an orthonormal basis Q: A rank-k matrix Q is found such that its columns form an orthonormal basis, and a related matrix S approximates the transpose of R. This is achieved using an SVD of R.
  3. Computing an intermediate matrix T: This is a simple matrix multiplication of A and Q.
  4. Computing the SVD of T: The SVD of T is computed to obtain matrices U, Σ, and W.
  5. Forming the final approximation: The final low-rank approximation is constructed using U, Σ, and V (derived from Q and W).

The paper also presents a "modified algorithm" (Subsection 4.3) and a "Blanczos" algorithm (Subsection 4.4) which offer variations in accuracy and computational cost, with the Blanczos algorithm being particularly robust to roundoff errors. The theoretical analysis relies heavily on lemmas concerning the singular values of general and random matrices, as well as properties of matrix norms.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and numerical experiments using synthetic data generated to test specific properties of the algorithm, such as varying singular value decay rates.

Key Insights and Ideas

  • Randomization for Accuracy: The core insight is that judicious use of random sampling, particularly by applying the matrix to random Gaussian vectors, can effectively capture the essential structure of a matrix for low-rank approximation, leading to surprisingly high accuracy.
  • Enhancing Singular Value Decay: Applying the matrix to powers of A^T A (or A A^T) before random sampling is a key technique to amplify the decay of smaller singular values, making them easier to distinguish from noise and thus improving approximation accuracy.
  • Near-Optimal Accuracy: The algorithm achieves accuracy remarkably close to the best possible (defined by the SVD), with the error bound being proportional to the (k+1)th singular value, scaled by a factor that depends on the matrix dimensions and a user-chosen parameter i.
  • Robustness to Slow Decay: Unlike many previous methods, this algorithm maintains high accuracy even when the singular values of the matrix decay slowly, a common scenario in real-world data.
  • Theoretical Guarantees: The paper provides strong theoretical guarantees on the accuracy of the approximation, holding with very high probability.

Key Results

  • The proposed randomized algorithm produces a rank-k approximation UΣV^T to a matrix A such that ||A - UΣV^T|| ≤ C * m^(1/(4i+2)) * σ_{k+1} with very high probability (typically > 1 - 10^-15). Here, σ_{k+1} is the (k+1)th largest singular value of A, and i is a parameter chosen by the user.
  • For practical choices of i (e.g., i=1 or i=2), the algorithm requires O(nmki) floating-point operations, making it efficient for large matrices.
  • Numerical experiments demonstrate that the algorithm's accuracy is superior to classical pivoted QR-decomposition methods, especially for matrices with slowly decaying singular values.
  • The "Blanczos" variant of the algorithm offers enhanced robustness to roundoff errors, making it a strong candidate for a general-purpose tool.

Limitations and Future Work

  • Theoretical Constant C: While the theoretical bound on accuracy is excellent, the constant C in the bound is not explicitly minimized and can be quite large theoretically. However, numerical experiments suggest that the actual constant is much smaller than the theoretical worst-case.
  • Parameter i: The parameter i influences the trade-off between accuracy and computational cost. While the paper suggests i=1 or i=2 are often sufficient, further research could explore optimal choices for i in different scenarios.
  • Computational Cost for Very Large i: While the algorithm is efficient for small i, the computational cost increases with i.
  • Future Work: The authors suggest that their analysis could be extended to other randomized algorithms for low-rank approximation. The robustness of the Blanczos algorithm is highlighted, suggesting its potential as a general-purpose tool. The paper also mentions that the algorithm is more efficient when A and A^T can be applied rapidly to arbitrary vectors, hinting at applications for sparse matrices.

Summary updated

Abstract

Principal component analysis (PCA) requires the computation of a low-rank approximation to a matrix containing the data being analyzed. In many applications of PCA, the best possible accuracy of any rank-deficient approximation is at most a few digits (measured in the spectral norm, relative to the spectral norm of the matrix being approximated). In such circumstances, efficient algorithms have not come with guarantees of good accuracy, unless one or both dimensions of the matrix being approximated are small. We describe an efficient algorithm for the low-rank approximation of matrices that produces accuracy that is very close to the best possible accuracy, for matrices of arbitrary sizes. We illustrate our theoretical results via several numerical examples.
BibTeX
@article{rokhlin2009randomized,
  author = {Vladimir Rokhlin and Arthur Szlam and Mark Tygert},
  title = {{A Randomized Algorithm for Principal Component Analysis.}},
  journal = {SIAM J. Matrix Analysis Applications2009},
  year = {2009},
  url = {https://openreview.net/forum?id=0JYDXZb2DLH},
}
Figure