Format

Send to

Choose Destination
ACM Trans Math Softw. 2017 Jan;43(3). pii: 28. doi: 10.1145/3004053.

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

Author information

1
Program in Applied Mathematics, 51 Prospect St., Yale University, New Haven, CT 06510.
2
Facebook, 8th floor, 770 Broadway, New York, NY 10003.
3
Yale University, School of Medicine, Department of Pathology, Suite 505L, 300 George St., New Haven, CT 06520.
4
Facebook, 1 Facebook Way, Menlo Park, CA 94025.

Abstract

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).

KEYWORDS:

Algorithms; PCA; Performance; Principal component analysis; SVD; singular value decomposition

Supplemental Content

Full text links

Icon for PubMed Central
Loading ...
Support Center