Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions

DOI10.1137/090771806zbMath1269.65043arXiv0909.4061OpenAlexW2117756735WikidataQ46236603 ScholiaQ46236603MaRDI QIDQ93618

Per-Gunnar Martinsson, Nathan Halko, Joel A. Tropp, Per-Gunnar Martinsson, Joel A. Tropp, Nathan Halko

Publication date: 22 September 2009

Published in: SIAM Review (Search for Journal in Brave)

Abstract: Low-rank matrix approximations, such as the truncated singular value decomposition and the rank-revealing QR decomposition, play a central role in data analysis and scientific computing. This work surveys and extends recent research which demonstrates that randomization offers a powerful tool for performing low-rank matrix approximation. These techniques exploit modern computational architectures more fully than classical methods and open the possibility of dealing with truly massive data sets. This paper presents a modular framework for constructing randomized algorithms that compute partial matrix decompositions. These methods use random sampling to identify a subspace that captures most of the action of a matrix. The input matrix is then compressed---either explicitly or implicitly---to this subspace, and the reduced matrix is manipulated deterministically to obtain the desired low-rank factorization. In many cases, this approach beats its classical competitors in terms of accuracy, speed, and robustness. These claims are supported by extensive numerical experiments and a detailed error analysis.

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

zbMATH Keywords

numerical examplessingular value decompositionprincipal component analysisdimension reductionrandomized algorithmdata analysisparallel algorithmrandom matrixKrylov subspace methodsscientific computingeigenvalue decompositionmatrix approximationinterpolative decompositionstreaming algorithmrank-revealing QR factorizationJohnson-lindenstrauss lemmapass-efficient algorithmsparse input matrix

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Random matrices (probabilistic aspects) (60B20) Parallel numerical computation (65Y05) Random matrices (algebraic aspects) (15B52) Randomized algorithms (68W20)

Related Items (only showing first 100 items - show all)

Generative modeling via tensor train sketching ⋮ Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions ⋮ Model Reduction for Nonlinear Systems by Balanced Truncation of State and Gradient Covariance ⋮ Full-rank and low-rank splitting methods for the Swift-Hohenberg equation ⋮ Randomized algorithms for the computation of multilinear rank-\((\mu_1,\mu_2,\mu_3)\) approximations ⋮ Statistical Inference, Learning and Models in Big Data ⋮ Robust Recovery of Low-Rank Matrices and Low-Tubal-Rank Tensors from Noisy Sketches ⋮ Gradient-Preserving Hyper-Reduction of Nonlinear Dynamical Systems via Discrete Empirical Interpolation ⋮ A literature survey of matrix methods for data science ⋮ Classification and image processing with a semi‐discrete scheme for fidelity forced Allen–Cahn on graphs ⋮ Deep learning methods for partial differential equations and related parameter identification problems ⋮ Deep learning‐based reduced order models for the real‐time simulation of the nonlinear dynamics of microstructures ⋮ Subsampling spectral clustering for stochastic block models in large-scale networks ⋮ Pass-efficient randomized LU algorithms for computing low-rank matrix approximation ⋮ Streaming Tensor Train Approximation ⋮ Interpolatory input and output projections for flow control ⋮ Quantum-inspired canonical correlation analysis for exponentially large dimensional data ⋮ An efficient randomized fixed-precision algorithm for tensor singular value decomposition ⋮ Online Principal Component Analysis in High Dimension: Which Algorithm to Choose? ⋮ Scalable methods for computing sharp extreme event probabilities in infinite-dimensional stochastic systems ⋮ Iterative rank-one matrix completion via singular value decomposition and nuclear norm regularization ⋮ Krylov-Aware Stochastic Trace Estimation ⋮ Randomized Low-Rank Approximation for Symmetric Indefinite Matrices ⋮ Randomized algorithms for orthogonal nonnegative matrix factorization ⋮ Parallel Algorithms for Computing the Tensor-Train Decomposition ⋮ Randomized Quasi-Optimal Local Approximation Spaces in Time ⋮ An Improved Analysis and Unified Perspective on Deterministic and Randomized Low-Rank Matrix Approximation ⋮ Practical sketching algorithms for low-rank Tucker approximation of large tensors ⋮ A new matrix maximization model for computing ratios of generalized singular values from high-order GSVD ⋮ Principled interpolation of Green's functions learned from data ⋮ Low tubal rank tensor completion based on singular value factors ⋮ Localized Model Reduction for Nonlinear Elliptic Partial Differential Equations: Localized Training, Partition of Unity, and Adaptive Enrichment ⋮ Optimal Reaction Coordinates: Variational Characterization and Sparse Computation ⋮ A Fast and Scalable Computational Framework for Large-Scale High-Dimensional Bayesian Optimal Experimental Design ⋮ Front transport reduction for complex moving fronts ⋮ Training very large scale nonlinear SVMs using alternating direction method of multipliers coupled with the hierarchically semi-separable kernel approximations ⋮ Efficient Natural Gradient Descent Methods for Large-Scale PDE-Based Optimization Problems ⋮ A Predictor-Corrector Strategy for Adaptivity in Dynamical Low-Rank Approximations ⋮ CECM: a continuous empirical cubature method with application to the dimensional hyperreduction of parameterized finite element models ⋮ Haar-like wavelets on hierarchical trees ⋮ Pass-efficient truncated UTV for low-rank approximations ⋮ Universal Features for High-Dimensional Learning and Inference ⋮ HODLR\(d\)D: a new black-box fast algorithm for \(N\)-body problems in \(d\)-dimensions with guaranteed error bounds. Applications to integral equations and support vector machines ⋮ A preconditioned iterative interior point approach to the conic bundle subproblem ⋮ A parallel low rank matrix optimization method for recovering Internet traffic network data via link flow measurement ⋮ Accelerated matrix completion algorithm using continuation strategy and randomized SVD ⋮ Solution of the EEG inverse problem by random dipole sampling ⋮ Stable probability of reduced matrix obtained by Gaussian random projection ⋮ A low-rank update for relaxed Schur complement preconditioners in fluid flow problems ⋮ A randomized algorithm for tensor singular value decomposition using an arbitrary number of passes ⋮ Randomized singular value decomposition for integrative subtype analysis of `omics data' using non-negative matrix factorization ⋮ Admissible subspaces and the subspace iteration method ⋮ Fast randomized numerical rank estimation for numerically low-rank matrices ⋮ Stable Rank-Adaptive Dynamically Orthogonal Runge–Kutta Schemes ⋮ Efficient Error and Variance Estimation for Randomized Matrix Computations ⋮ PyAlbany: a Python interface to the C++ multiphysics solver Albany ⋮ Spectral deviation of concentration operators for the short-time Fourier transform ⋮ A fast randomized algorithm for computing an approximate null space ⋮ Explicit deflation in Golub-Kahan-Lanczos bidiagonalization methods ⋮ On randomized sketching algorithms and the Tracy-Widom law ⋮ Hierarchical off-diagonal low-rank approximation of Hessians in inverse problems, with application to ice sheet model initialization ⋮ A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization ⋮ Randomized Low-Rank Approximation of Monotone Matrix Functions ⋮ Learning to Forecast Dynamical Systems from Streaming Data ⋮ A data-driven and model-based accelerated Hamiltonian Monte Carlo method for Bayesian elliptic inverse problems ⋮ Low-Rank Tensor Approximations for Solving Multimarginal Optimal Transport Problems ⋮ Enabling Hyper-Differential Sensitivity Analysis for Ill-Posed Inverse Problems ⋮ PCA Sparsified ⋮ Scalable Physics-Based Maximum Likelihood Estimation Using Hierarchical Matrices ⋮ Large Deviation Theory-based Adaptive Importance Sampling for Rare Events in High Dimensions ⋮ XT<scp>race</scp>: Making the Most of Every Sample in Stochastic Trace Estimation ⋮ UTV decomposition of dual matrices and its applications ⋮ Space-Time Reduced Basis Methods for Parametrized Unsteady Stokes Equations ⋮ Projection-based reduced order models for parameterized nonlinear time-dependent problems arising in cardiac mechanics ⋮ Fast macroscopic forcing method ⋮ Derivative-informed neural operator: an efficient framework for high-dimensional parametric derivative learning ⋮ Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition ⋮ Piecewise DMD for oscillatory and Turing spatio-temporal dynamics ⋮ Randomized low rank approximation for nonnegative pure quaternion matrices ⋮ Adaptive symplectic model order reduction of parametric particle-based Vlasov–Poisson equation ⋮ Unnamed Item ⋮ Accurate and fast matrix factorization for low-rank learning. ⋮ Constructing low-rank Tucker tensor approximations using generalized completion ⋮ Sparse POD modal subsets for reduced-order nonlinear explicit dynamics ⋮ Solving PDEs on unknown manifolds with machine learning ⋮ Subspace Acceleration for a Sequence of Linear Systems and Application to Plasma Simulation ⋮ Estimation of binary time-frequency masks from ambient noise ⋮ Reduced-order models for array structures mounted on platforms with parameters variations ⋮ Randomized estimation of functional covariance operator via subsampling ⋮ Point spread function approximation of high-rank Hessians with locally supported nonnegative integral kernels ⋮ Randomized block Krylov subspace algorithms for low-rank quaternion matrix approximations ⋮ Efficient truncated randomized SVD for mesh-free kernel methods ⋮ A noninvasive system-level model order reduction scheme for flexible multibody simulation ⋮ 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 ⋮ Recent advancements in preconditioning techniques for large size linear systems suited for high performance computing ⋮ Randomized dynamic mode decomposition for nonintrusive reduced order modelling ⋮ Preconditioner design via Bregman divergences ⋮ Fast and accurate randomized algorithms for linear systems and eigenvalue problems ⋮ SVD-based algorithms for fully-connected tensor network decomposition

This page was built for publication: Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions