An Algorithm for the Principal Component Analysis of Large Data Sets

By Nathan Halko, Per-Gunnar Martinsson, Yoel Shkolnisky, Mark Tygert. 2010

308 citations recorded by the source corpus.

Recently popularized randomized methods for principal component analysis (PCA) efficiently and reliably produce nearly optimal accuracy—even on parallel processors—unlike the classical (deterministic) alternatives. We adapt one of these randomized methods for use with data sets that are too large to be stored in random-access memory (RAM). (The traditional terminology is that our procedure works efficiently out-of-core.) We illustrate the performance of the algorithm via several numerical examples. For example, we report on the PCA of a data set stored on disk that is so large that less than a hundredth of it can fit in our computer's RAM.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition

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 Computational Mechanics

In Computer Vision and Pattern Recognition

Citations in the corpus

Fast Interpolation-based t-SNE for Improved Visualization of Single-Cell RNA-Seq Data (2017, methodology): “ which are easily parallelized, and for which highly optimized implementations exist. Randomized algorithms have been rigorously proven to be remarkably accurate with extremely high probability (e.g. Halko et al. (2011b); Witten and Candes (2015)), because for a rank-kmatrix, as few as l= k+2 random”
Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition (2015, methodology): “An alternative, uesd in [1], [19], and our Algorithm 2, is to compute K explicitly and then find Q using a QR decomposition.”
TAU-REX I: A NEXT GENERATION RETRIEVAL CODE FOR EXOPLANETARY ATMOSPHERES (2014, methodology): “Due to the large size of the matrices involved, we approximate equation 9 with a randomised, truncated SVD algorithm (Halko et al. 2011; Martinsson et al. 2011).”
Handbook of Big Data (2016, background): “” to pan so the crosshair location becomes the center of the view – [ ”, “ ] , { ”, “ } to pan so the crosshair location becomes, respectively, the bottom left, the bottom right, the top left, or the top right of the view.”
A high-bias, low-variance introduction to Machine Learning for physicists (2018, unknown): “In the case of PCA, if one is only interested in a small fraction of the principal components with largest variance (which is usually the case), efficient implementations based on Lanczos methods can achieve scaling of O(N2) for dense matrices (Halko et al., 2011).”
Fast Principal Component Analysis of Large-Scale Genome-Wide Data (2014, background): “In recent years, research into randomized matrix algorithms has yielded alternative approaches for performing PCA and producing these top PCs, while being far more computationally tractable and maintaining high accuracy relative to the traditional ‘‘exact’’ algorithms [4,5].”
Using Geodesic Space Density Gradients for Network Community Detection (2017, methodology): “[24] have used a randomized version of the block Lanczos method for computing SVD of large matrices hav-”
Randomized numerical linear algebra: Foundations and algorithms (2020, methodology): “See Halko et al. (2011a) for much more information.”
Randomized Matrix Decompositions using R (2016, methodology): “Eventually, the seminal work by Halko et al. (2011b) uniﬁed and expanded previous work on the randomized singular value decomposition and introduced state-of-the-art prototype algorithms to compute the near-optimal low-rank singular value decomposition.”
AVEC 2016: Depression, Mood, and Emotion Recognition Workshop and Challenge (2016, methodology): “A feature reduction is then performed by applying a Principal Component Analysis (PCA) from a low-rank (up to rank 500) approximation [18].”
Efficient Algorithms for t-distributed Stochastic Neighborhood Embedding (2017, methodology): “50) principal components of a dataset to high accuracy, without ever loading it in its entirety (Halko et al. (2011a)).”
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].”