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