A randomized algorithm for principal component analysis

DOI10.1137/080736417zbMATH Open1198.65035arXiv0809.2274OpenAlexW2040387238MaRDI QIDQ3584149FDOQ3584149

Authors: Arthur Szlam, Mark Tygert, Vladimir Rokhlin 

Publication date: 19 August 2010

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

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 very close to the best possible, for matrices of arbitrary sizes. We illustrate our theoretical results via several numerical examples.

Full work available at URL: https://arxiv.org/abs/0809.2274

Recommendations

• An algorithm for the principal component analysis of large data sets
• Randomized algorithms for distributed computation of principal component analysis and singular value decomposition
• A fast randomized algorithm for the approximation of matrices
• Algorithm 971
• Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix

zbMATH Keywords

principal component analysisnumerical examplessingular value decompositionlow-rank approximationalgorithm

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Randomized algorithms (68W20)

Cited In (70)

• Fixed-precision randomized low-rank approximation methods for nonlinear model order reduction of large systems
• Randomized low-rank approximation methods for projection-based model order reduction of large nonlinear dynamical problems
• Fast and accurate randomized algorithms for linear systems and eigenvalue problems
• Fast Randomized Non-Hermitian Eigensolvers Based on Rational Filtering and Matrix Partitioning
• Parameter identification by deep learning of a material model for granular media
• Practical sketching algorithms for low-rank Tucker approximation of large tensors
• Flip-flop spectrum-revealing QR factorization and its applications to singular value decomposition
• A class of refined preconditioners with sparse error correction for BEM linear system
• Pass-efficient randomized algorithms for low-rank matrix approximation using any number of views
• Algorithm 971
• Fast randomized iteration: diffusion Monte Carlo through the Lens of numerical linear algebra
• Multiscale geometric methods for data sets. I: Multiscale SVD, noise and curvature.
• Single-pass randomized QLP decomposition for low-rank approximation
• Randomized QLP decomposition
• Randomized block Krylov methods for approximating extreme eigenvalues
• Principal component projection with low-degree polynomials
• Stochastic boundary methods of fundamental solutions for solving PDEs
• The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection
• Multi-scale geometric methods for data sets. II: Geometric multi-resolution analysis
• Detecting low-rank clusters via random sampling
• A randomized singular value decomposition for third-order oriented tensors
• Randomized numerical linear algebra: Foundations and algorithms
• Optimal algorithms for binary, sparse, and \(L_1\)-norm principal component analysis
• Randomized near-neighbor graphs, giant components and applications in data science
• Randomized singular spectrum analysis for long time series
• Accurate low-rank approximations via a few iterations of alternating least squares
• System identification via CUR-factored Hankel approximation
• Randomized algorithms for distributed computation of principal component analysis and singular value decomposition
• Fast and Accurate Proper Orthogonal Decomposition using Efficient Sampling and Iterative Techniques for Singular Value Decomposition
• Compressed principal component analysis of non-Gaussian vectors
• Efficient algorithms for CUR and interpolative matrix decompositions
• Towards theory of generic principal component analysis
• Efficient preconditioning for noisy separable nonnegative matrix factorization problems by successive projection based low-rank approximations
• A kernel-independent sum-of-exponentials method
• Sparsified randomization algorithms for low rank approximations and applications to integral equations and inhomogeneous random field simulation
• Fast Cadzow's algorithm and a gradient variant
• Sketching for principal component regression
• Subspace Iteration Randomization and Singular Value Problems
• Algorithm 1022: Efficient Algorithms for Computing a Rank-Revealing UTV Factorization on Parallel Computing Architectures
• A principal component analysis algorithm with invariant norm
• A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices
• Efficient randomized algorithms for the fixed-precision low-rank matrix approximation
• Subspaces analysis for random projection UTV framework
• Title not available (Why is that?)
• Hierarchical Approximate Proper Orthogonal Decomposition
• Randomized quaternion QLP decomposition for low-rank approximation
• Randomized Dynamic Mode Decomposition
• Modified truncated randomized singular value decomposition (MTRSVD) algorithms for large scale discrete ill-posed problems with general-form regularization
• Randomized generalized singular value decomposition
• Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations
• An algorithm for the principal component analysis of large data sets
• Accelerating large partial EVD/SVD calculations by filtered block Davidson methods
• Convolutional neural network learning for generic data classification
• Clustered matrix approximation
• Stochastic algorithms in linear algebra -- beyond the Markov chains and von Neumann-Ulam scheme
• Principal components: a descent algorithm
• Recovering PCA and sparse PCA via hybrid-\((\ell_1,\ell_2)\) sparse sampling of data elements
• Literature survey on low rank approximation of matrices
• Title not available (Why is that?)
• Randomized local model order reduction
• A covariance-free iterative algorithm for distributed principal component analysis on vertically partitioned data
• Approximating matrix eigenvalues by subspace iteration with repeated random sparsification
• Optimal principal component analysis in distributed and streaming models
• Streaming low-rank matrix approximation with an application to scientific simulation
• An efficient algorithm for weighted PCA
• A consistency theorem for randomized singular value decomposition
• Data-reducing principal component analysis (PCA) is NP-hard even under the simplest interval uncertainty
• A stochastic variance reduction method for PCA by an exact penalty approach
• Randomized algorithms for low-rank matrix factorizations: sharp performance bounds
• The singular value decomposition: anatomy of optimizing an algorithm for extreme scale

This page was built for publication: A randomized algorithm for principal component analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3584149)