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

DOI10.48550/arXiv.0909.4061zbMath1269.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)

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. ⋮ Algorithm 1022: Efficient Algorithms for Computing a Rank-Revealing UTV Factorization on Parallel Computing Architectures ⋮ Low-Rank Covariance Function Estimation for Multidimensional Functional Data ⋮ Efficient Identification of Butterfly Sparse Matrix Factorizations ⋮ An Offline-Online Decomposition Method for Efficient Linear Bayesian Goal-Oriented Optimal Experimental Design: Application to Optimal Sensor Placement ⋮ Randomized Algorithms for Rounding in the Tensor-Train Format ⋮ Randomized numerical linear algebra: Foundations and algorithms ⋮ Learning physics-based models from data: perspectives from inverse problems and model reduction ⋮ Adaptive Geometric Multiscale Approximations for Intrinsically Low-dimensional Data ⋮ Regularization via Mass Transportation ⋮ Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA ⋮ State-Based Adjoint Method for Reduced Order Modeling ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Low-Rank Correction Methods for Algebraic Domain Decomposition Preconditioners ⋮ Randomized QR with Column Pivoting

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