A Randomized Algorithm for Principal Component Analysis

By Vladimir Rokhlin, Arthur Szlam, Mark Tygert. 2008

471 citations recorded by the source corpus.

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.

Subfields: Computational Mathematics, Computational Mechanics, Statistics and Probability, Numerical Methods & Scientific Computing, Signal Processing

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 Statistics and Probability

In Numerical Methods & Scientific Computing

In Signal Processing

Citations in the corpus

Development and evaluation of gappy-POD as a data reconstruction technique for noisy PIV measurements in gas turbine combustors (2016, methodology): “Here, a block-Lanczos method is used to approximate the singular value decomposition (SVD) of R (Rokhlin et al, 2009).”
GPU accelerated t-distributed stochastic neighbor embedding (2019, methodology): “A significant number of techniques have been proposed to do such dimensionality reduction with classical methods such as principal component analysis [13], [14], multi-dimensional scaling [15], and more modern methods such as Sammon mapping [16], curvilinear component analysis [17], stochastic neigh”
T-SNE-CUDA: GPU-Accelerated T-SNE and its Applications to Modern Data (2018, methodology): “In addition to t-SNE, other methods have been explored by data scientists and vision researchers to visualize high dimensional data such as Sammon Mapping [24], Isomap [26], Locally Linear Embedding [21], Randomized Principle Component Analysis [20] and Johnson-Lindenstrauss Embedding [12].”
Revisiting the Nystrom Method for Improved Large-scale Machine Learning (2013, background): “ream interest [54, 48]. Third, in recent years several high-quality numerical implementations of randomized matrix algorithms for least-squares and low-rank approximation problems have been developed [3, 50, 65, 55, 49]. These have been developed from a “scientiﬁc computing” perspective, where condi”
Learning Discriminative Appearance-Based Models Using Partial Least Squares (2009, methodology): “Since the high dimensionality of the feature space poses difficulties to compute the covariance matrix for PCA, we use a randomized PCA algorithm [ 14 ].”
Application of t-SNE to Human Genetic Data (2017, background): “Of course, in specialized applications such as sparse matrix, approximate results, or partial results, the computational complexity can be improved [49, 50, 51].”
Divide-and-Conquer Matrix Factorization (2011, methodology): “Inspired by this result, several random projection algorithms [e.g., 32, 22, 35] have been introduced for approximating a matrix by projecting it onto a random low-dimensional subspace (see Halko et al. [13] for further discussion).”
Machine Learning for Fluid Mechanics (2019, methodology): “This non-linearity may come however at the expense of losing the inverse relationship between the encoder and decoder functions that is one of the strengths of linear PCA.”
Randomized Matrix Decompositions using R (2016, methodology): “The second method for improving the quality of the basis Q involves the concept of power sampling iterations (Rokhlin et al. 2009; Halko et al. 2011b; Gu 2015).”
Fast nonnegative deconvolution for spike train inference from population calcium imaging. (2009, result): “methods to initiali ze the spatial ﬁlters (such as “independentcomponentanalysis” [30]) could also work, be cause fast algorithms for computing the ﬁrst few principal components are readily available [31], PCA was both sufﬁcie ntly effective and efﬁcient. Given these initializations, estimating α~ a”
Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition (2015, methodology): “Even though the algorithm has been discussed and tested for potential improvement over Simultaneous Iteration [1, 19, 20], theoretical bounds for Krylov subspace and Lanczos methods are much more limited.”