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