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)

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

zbMATH Keywords

numerical examples singular value decomposition principal component analysis dimension reduction randomized algorithm data analysis parallel algorithm random matrix Krylov subspace methods scientific computing eigenvalue decomposition matrix approximation interpolative decomposition streaming algorithm rank-revealing QR factorization Johnson-lindenstrauss lemma pass-efficient algorithm sparse 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)

Efficiency of randomised dynamic mode decomposition for reduced order modelling ⋮ Exploiting low-rank structure in semidefinite programming by approximate operator splitting ⋮ Data-Driven Balancing of Linear Dynamical Systems ⋮ Active Subspace of Neural Networks: Structural Analysis and Universal Attacks ⋮ Low-Rank Tucker Approximation of a Tensor from Streaming Data ⋮ Approximating Matrix Eigenvalues by Subspace Iteration with Repeated Random Sparsification ⋮ Manifold Learning and Nonlinear Homogenization ⋮ Randomized Spectral Clustering in Large-Scale Stochastic Block Models ⋮ A Distance-Preserving Matrix Sketch ⋮ Structured Matrix Approximations via Tensor Decompositions ⋮ A Nonlinear Matrix Decomposition for Mining the Zeros of Sparse Data ⋮ Modern Koopman Theory for Dynamical Systems ⋮ A machine learning approach to optimal Tikhonov regularization I: Affine manifolds ⋮ On expected error of randomized Nyström kernel regression ⋮ Improved Variants of the Hutch++ Algorithm for Trace Estimation ⋮ Randomized Quaternion Singular Value Decomposition for Low-Rank Matrix Approximation ⋮ Selecting Regularization Parameters for Nuclear Norm--Type Minimization Problems ⋮ Subspaces Analysis for Random Projection UTV Framework ⋮ Fast deflation sparse principal component analysis via subspace projections ⋮ hm-toolbox: MATLAB Software for HODLR and HSS Matrices ⋮ Trading Beams for Bandwidth: Imaging with Randomized Beamforming ⋮ Unnamed Item ⋮ The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection ⋮ Interpolative Decomposition Butterfly Factorization ⋮ Scalable Optimization-Based Sampling on Function Space ⋮ Randomized Discrete Empirical Interpolation Method for Nonlinear Model Reduction ⋮ Analysis of amplification mechanisms and cross-frequency interactions in nonlinear flows via the harmonic resolvent ⋮ Randomized Sampling for Basis Function Construction in Generalized Finite Element Methods ⋮ Randomized matrix approximation to enhance regularized projection schemes in inverse problems ⋮ Regularized Linear Inversion with Randomized Singular Value Decomposition ⋮ Variational Gaussian approximation for Poisson data ⋮ Variable Projection Methods for an Optimized Dynamic Mode Decomposition ⋮ Low Rank Approximation of a Sparse Matrix Based on LU Factorization with Column and Row Tournament Pivoting ⋮ Randomized Subspace Iteration: Analysis of Canonical Angles and Unitarily Invariant Norms ⋮ Concentration of the Frobenius Norm of Generalized Matrix Inverses ⋮ On the Best Approximation of the Hierarchical Matrix Product ⋮ Random Sampling and Efficient Algorithms for Multiscale PDEs ⋮ Hierarchical Matrix Approximations of Hessians Arising in Inverse Problems Governed by PDEs ⋮ Sparse Solutions in Optimal Control of PDEs with Uncertain Parameters: The Linear Case ⋮ Spatio-temporal proper orthogonal decomposition of turbulent channel flow ⋮ Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations ⋮ Globally Constructed Adaptive Local Basis Set for Spectral Projectors of Second Order Differential Operators ⋮ Randomized Approach to Nonlinear Inversion Combining Random and Optimized Simultaneous Sources and Detectors ⋮ Randomized Residual-Based Error Estimators for Parametrized Equations ⋮ Analytical Low-Rank Compression via Proxy Point Selection ⋮ Krylov Methods for Low-Rank Regularization ⋮ Tensor Train Construction From Tensor Actions, With Application to Compression of Large High Order Derivative Tensors ⋮ The AZ Algorithm for Least Squares Systems with a Known Incomplete Generalized Inverse ⋮ Estimating Higher-Order Moments Using Symmetric Tensor Decomposition ⋮ On Soft Errors in the Conjugate Gradient Method: Sensitivity and Robust Numerical Detection ⋮ Optimization-Based Markov Chain Monte Carlo Methods for Nonlinear Hierarchical Statistical Inverse Problems ⋮ A Data-Driven Approach for Multiscale Elliptic PDEs with Random Coefficients Based on Intrinsic Dimension Reduction ⋮ Fast Approximation of the Gauss--Newton Hessian Matrix for the Multilayer Perceptron ⋮ Norm and Trace Estimation with Random Rank-one Vectors ⋮ Preserving Positive Definiteness in Hierarchically Semiseparable Matrix Approximations ⋮ FANOK: Knockoffs in Linear Time ⋮ On the Numerical Rank of Radial Basis Function Kernels in High Dimensions ⋮ Singular Value Decomposition Approximation via Kronecker Summations for Imaging Applications ⋮ A New Preconditioner that Exploits Low-Rank Approximations to Factorization Error ⋮ Adapting Regularized Low-Rank Models for Parallel Architectures ⋮ Unnamed Item ⋮ Uniform Error Estimates for the Lanczos Method ⋮ Taylor Approximation for Chance Constrained Optimization Problems Governed by Partial Differential Equations with High-Dimensional Random Parameters ⋮ Shallow neural networks for fluid flow reconstruction with limited sensors ⋮ Robust and Effective eSIF Preconditioning for General Dense SPD Matrices ⋮ Fast Randomized Non-Hermitian Eigensolvers Based on Rational Filtering and Matrix Partitioning ⋮ An Optimal-Storage Approach to Semidefinite Programming Using Approximate Complementarity ⋮ Rapid Application of the Spherical Harmonic Transform via Interpolative Decomposition Butterfly Factorization ⋮ Two-Level Nyström--Schur Preconditioner for Sparse Symmetric Positive Definite Matrices ⋮ The nonequilibrium quantum many-body problem as a paradigm for extreme data science ⋮ Acoustic full-waveform inversion and its uncertainty estimation based on a vector-version square-root variable metric method ⋮ Pass-Efficient Randomized Algorithms for Low-Rank Matrix Approximation Using Any Number of Views ⋮ Distributed Robust Subspace Recovery ⋮ Hierarchical Approximate Proper Orthogonal Decomposition ⋮ Low-Rank Independence Samplers in Hierarchical Bayesian Inverse Problems ⋮ Improving the Complexity of Block Low-Rank Factorizations with Fast Matrix Arithmetic ⋮ Sharp error bounds for Ritz vectors and approximate singular vectors ⋮ Randomized singular spectrum analysis for long time series ⋮ Unnamed Item ⋮ Efficient Construction of an HSS Preconditioner for Symmetric Positive Definite $\mathcal{H}^2$ Matrices ⋮ Data-driven resolvent analysis ⋮ Randomized Sketching Algorithms for Low-Memory Dynamic Optimization ⋮ A Low-Rank Schwarz Method for Radiative Transfer Equation With Heterogeneous Scattering Coefficient ⋮ Hierarchical algorithms on hierarchical architectures ⋮ Numerical algorithms for high-performance computational science ⋮ Efficient Algorithms for Eigensystem Realization Using Randomized SVD ⋮ Scalable Semidefinite Programming ⋮ Sampled limited memory methods for massive linear inverse problems ⋮ Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning ⋮ Low-Rank Matrix Estimation from Rank-One Projections by Unlifted Convex Optimization ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Sublinear Cost Low Rank Approximation via Subspace Sampling ⋮ Matrix Rigidity and the Ill-Posedness of Robust PCA and Matrix Completion ⋮ Randomized Algorithms for Low-Rank Tensor Decompositions in the Tucker Format ⋮ A Hierarchical Preconditioner for Wave Problems in Quasilinear Complexity

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