Algorithm 971: An Implementation of a Randomized Algorithm for Principal Component Analysis

By Huamin Li, George C. Linderman, Arthur Szlam, Kelly P. Stanton, Yuval Kluger, Mark Tygert. 2017

69 citations recorded by the source corpus.

Recent years have witnessed intense development of randomized methods for low-rank approximation. These methods target principal component analysis and the calculation of truncated singular value decompositions. The present article presents an essentially black-box, foolproof implementation for Mathworks’ MATLAB, a popular software platform for numerical computation. As illustrated via several tests, the randomized algorithms for low-rank approximation outperform or at least match the classical deterministic techniques (such as Lanczos iterations run to convergence) in basically all respects: accuracy, computational efficiency (both speed and memory usage), ease-of-use, parallelizability, and reliability. However, the classical procedures remain the methods of choice for estimating spectral norms and are far superior for calculating the least singular values and corresponding singular vectors (or singular subspaces).

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics, Computational Mechanics

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

In Atomic and Molecular Physics, and Optics

In Computational Mechanics

Citations in the corpus

Fast Interpolation-based t-SNE for Improved Visualization of Single-Cell RNA-Seq Data (2017, methodology): “to be negligible. The algorithm and its underlying theory are covered in detail in Halko et al. (2011b). An easy-to-use \black box" implementation of randomized PCA is available and described in Li et al. (2017), but it requires the entire matrix to be loaded in the memory. We present an out-of”
Efficient Algorithms for t-distributed Stochastic Neighborhood Embedding (2017, methodology): “By simply replacing the matrix multiplications in Li et al. (2017)’s implementation with blockwise matrix multiplication, an out-of-core algorithm can be obtained.”
Randomized Near Neighbor Graphs, Giant Components, and Applications in Data Science (2017, unknown): “We then computed the ﬁrst ten principal components (PCs) using randomized principal component analysis [15] and performed subsequent analysis on the PCs.”
Randomized numerical linear algebra: Foundations and algorithms (2020, methodology): “See Algorithm 16 for a numerically stable implementation adapted from (Li et al. 2017, Tropp et al. 2017a).”