A Randomized Algorithm for Principal Component Analysis

DOI10.1137/080736417zbMath1198.65035arXiv0809.2274OpenAlexW2040387238MaRDI QIDQ3584149

Arthur D. Szlam, Mark Tygert, Vladimir Rokhlin

Publication date: 19 August 2010

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

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

zbMATH Keywords

algorithmnumerical examplessingular value decompositionprincipal component analysislow-rank approximation

Mathematics Subject Classification ID

Related Items (49)

Algorithm 1022: Efficient Algorithms for Computing a Rank-Revealing UTV Factorization on Parallel Computing Architectures ⋮ Approximating Matrix Eigenvalues by Subspace Iteration with Repeated Random Sparsification ⋮ Efficient algorithms for CUR and interpolative matrix decompositions ⋮ Randomized numerical linear algebra: Foundations and algorithms ⋮ Randomized Local Model Order Reduction ⋮ Efficient preconditioning for noisy separable nonnegative matrix factorization problems by successive projection based low-rank approximations ⋮ The Singular Value Decomposition: Anatomy of Optimizing an Algorithm for Extreme Scale ⋮ Accelerating large partial EVD/SVD calculations by filtered block Davidson methods ⋮ Principal components: a descent algorithm ⋮ Randomized quaternion QLP decomposition for low-rank approximation ⋮ Modified truncated randomized singular value decomposition (MTRSVD) algorithms for large scale discrete ill-posed problems with general-form regularization ⋮ Multiscale geometric methods for data sets. I: Multiscale SVD, noise and curvature. ⋮ Randomized QLP decomposition ⋮ Randomized generalized singular value decomposition ⋮ Efficient Randomized Algorithms for the Fixed-Precision Low-Rank Matrix Approximation ⋮ Subspaces Analysis for Random Projection UTV Framework ⋮ Fast Randomized Iteration: Diffusion Monte Carlo through the Lens of Numerical Linear Algebra ⋮ A kernel-independent sum-of-exponentials method ⋮ Practical sketching algorithms for low-rank Tucker approximation of large tensors ⋮ 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 ⋮ A class of refined preconditioners with sparse error correction for BEM linear system ⋮ The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection ⋮ Literature survey on low rank approximation of matrices ⋮ Convolutional neural network learning for generic data classification ⋮ A randomized singular value decomposition for third-order oriented tensors ⋮ System Identification via CUR-Factored Hankel Approximation ⋮ Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations ⋮ Randomized near-neighbor graphs, giant components and applications in data science ⋮ 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 ⋮ Hierarchical Approximate Proper Orthogonal Decomposition ⋮ Randomized Dynamic Mode Decomposition ⋮ Randomized singular spectrum analysis for long time series ⋮ Stochastic Algorithms in Linear Algebra - beyond the Markov Chains and von Neumann - Ulam Scheme ⋮ Stochastic boundary methods of fundamental solutions for solving PDEs ⋮ Fast Cadzow's algorithm and a gradient variant ⋮ Flip-flop spectrum-revealing QR factorization and its applications to singular value decomposition ⋮ A consistency theorem for randomized singular value decomposition ⋮ Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation ⋮ A Randomized Blocked Algorithm for Efficiently Computing Rank-revealing Factorizations of Matrices ⋮ Randomized block Krylov methods for approximating extreme eigenvalues ⋮ Clustered Matrix Approximation ⋮ Subspace Iteration Randomization and Singular Value Problems ⋮ Unnamed Item ⋮ Randomized algorithms for low-rank matrix factorizations: sharp performance bounds ⋮ Fast and Accurate Proper Orthogonal Decomposition using Efficient Sampling and Iterative Techniques for Singular Value Decomposition ⋮ Single-pass randomized QLP decomposition for low-rank approximation ⋮ Accurate Low-Rank Approximations Via a Few Iterations of Alternating Least Squares

This page was built for publication: A Randomized Algorithm for Principal Component Analysis