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 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)

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 ⋮ Cubature, Approximation, and Isotropy in the Hypercube ⋮ Sketching for a low-rank nonnegative matrix approximation: numerical study ⋮ Scalable subspace methods for derivative-free nonlinear least-squares optimization ⋮ Dynamically Orthogonal Runge–Kutta Schemes with Perturbative Retractions for the Dynamical Low-Rank Approximation ⋮ PLSS: A Projected Linear Systems Solver ⋮ A fast direct boundary element method for 3D acoustic problems based on hierarchical matrices ⋮ A compact heart iteration for low-rank approximations of large matrices ⋮ A Distributed-Memory Randomized Structured Multifrontal Method for Sparse Direct Solutions ⋮ Recompression of Hadamard Products of Tensors in Tucker Format ⋮ The engine behind (wall) turbulence: perspectives on scale interactions ⋮ Goal-Oriented Optimal Approximations of Bayesian Linear Inverse Problems ⋮ Analyzing the Effect of Local Rounding Error Propagation on the Maximal Attainable Accuracy of the Pipelined Conjugate Gradient Method ⋮ Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces ⋮ Sketching for Principal Component Regression ⋮ Fast Estimation of Approximate Matrix Ranks Using Spectral Densities ⋮ Continuous-time Random Walks for the Numerical Solution of Stochastic Differential Equations ⋮ The Golden-Thompson inequality: Historical aspects and random matrix applications ⋮ Adaptively Compressed Polarizability Operator for Accelerating Large Scale Ab Initio Phonon Calculations ⋮ Preconditioning Orbital Minimization Method for Planewave Discretization ⋮ Exploring the Locally Low Dimensional Structure in Solving Random Elliptic PDEs ⋮ Householder QR Factorization With Randomization for Column Pivoting (HQRRP) ⋮ Interpolative Butterfly Factorization ⋮ The Inverse Fast Multipole Method: Using a Fast Approximate Direct Solver as a Preconditioner for Dense Linear Systems ⋮ Fast Hierarchical Solvers For Sparse Matrices Using Extended Sparsification and Low-Rank Approximation ⋮ Low-Rank Tensor Recovery using Sequentially Optimal Modal Projections in Iterative Hard Thresholding (SeMPIHT) ⋮ An inverse‐free ADI algorithm for computing Lagrangian invariant subspaces ⋮ Randomized algorithms for generalized Hermitian eigenvalue problems with application to computing Karhunen–Loève expansion ⋮ Computing with Functions in Spherical and Polar Geometries I. The Sphere ⋮ Compressing Rank-Structured Matrices via Randomized Sampling ⋮ Low-Rank Approximation of a Matrix: Novel Insights, New Progress, and Extensions ⋮ Parameter Selection and Verification Techniques Based on Global Sensitivity Analysis Illustrated for an HIV Model ⋮ Block classical Gram–Schmidt-based block updating in low-rank matrix approximation ⋮ Block Basis Factorization for Scalable Kernel Evaluation ⋮ A spectral series approach to high-dimensional nonparametric regression ⋮ Randomized Dynamic Mode Decomposition ⋮ Fast Coulomb Matrix Construction via Compressing the Interactions Between Continuous Charge Distributions ⋮ PRIMME_SVDS: A High-Performance Preconditioned SVD Solver for Accurate Large-Scale Computations ⋮ Flip-flop spectrum-revealing QR factorization and its applications to singular value decomposition ⋮ Gradient-Free Construction of Active Subspaces for Dimension Reduction in Complex Models with Applications to Neutronics ⋮ Matrix Completion With Covariate Information ⋮ Finding Low-Rank Solutions via Nonconvex Matrix Factorization, Efficiently and Provably ⋮ The Steerable Graph Laplacian and its Application to Filtering Image Datasets ⋮ Fast Low-Rank Kernel Matrix Factorization Using Skeletonized Interpolation ⋮ Randomized GPU Algorithms for the Construction of Hierarchical Matrices from Matrix-Vector Operations ⋮ Scalable Matrix-Free Adaptive Product-Convolution Approximation for Locally Translation-Invariant Operators ⋮ Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation ⋮ CoordinateWise Descent Methods for Leading Eigenvalue Problem ⋮ Fiber Sampling Approach to Canonical Polyadic Decomposition and Application to Tensor Completion ⋮ Parallel Transport Unfolding: A Connection-Based Manifold Learning Approach ⋮ A scalable estimator of sets of integral operators ⋮ Efficient Marginalization-Based MCMC Methods for Hierarchical Bayesian Inverse Problems ⋮ Robust and Accurate Stopping Criteria for Adaptive Randomized Sampling in Matrix-Free Hierarchically Semiseparable Construction ⋮ Multiway Monte Carlo Method for Linear Systems ⋮ Coupled Canonical Polyadic Decompositions and (Coupled) Decompositions in Multilinear Rank- $(L_{r,n},L_{r,n},1)$ Terms---Part II: Algorithms ⋮ An Efficient Gauss--Newton Algorithm for Symmetric Low-Rank Product Matrix Approximations ⋮ Computationally Efficient Decompositions of Oblique Projection Matrices ⋮ Randomized Approximation of the Gram Matrix: Exact Computation and Probabilistic Bounds ⋮ ASKIT: Approximate Skeletonization Kernel-Independent Treecode in High Dimensions ⋮ Subspace Iteration Randomization and Singular Value Problems ⋮ Mixed-Precision Cholesky QR Factorization and Its Case Studies on Multicore CPU with Multiple GPUs ⋮ Inverse Heat Source Problem and Experimental Design for Determining Iron Loss Distribution ⋮ Butterfly Factorization Via Randomized Matrix-Vector Multiplications ⋮ Perturbations of CUR Decompositions ⋮ A Block Bidiagonalization Method for Fixed-Accuracy Low-Rank Matrix Approximation ⋮ Data-Driven Algorithms for Signal Processing with Trigonometric Rational Functions ⋮ PDE-Aware Deep Learning for Inverse Problems in Cardiac Electrophysiology ⋮ Bridging and Improving Theoretical and Computational Electrical Impedance Tomography via Data Completion ⋮ Gaussian Process Subspace Prediction for Model Reduction ⋮ Randomized Gram--Schmidt Process with Application to GMRES ⋮ Optimal Local Approximation Spaces for Parabolic Problems ⋮ Fast and Accurate Proper Orthogonal Decomposition using Efficient Sampling and Iterative Techniques for Singular Value Decomposition ⋮ An accelerated randomized Kaczmarz method via low-rank approximation ⋮ Butterfly Factorization ⋮ A Tale of Two Bases: Local-Nonlocal Regularization on Image Patches with Convolution Framelets ⋮ Fast state tomography with optimal error bounds ⋮ Accurate Low-Rank Approximations Via a Few Iterations of Alternating Least Squares ⋮ Fast approximate computations with Cauchy matrices and polynomials ⋮ Efficient global resolvent analysis via the one-way Navier–Stokes equations ⋮ Spectral decomposition of atomic structures in heterogeneous cryo-EM ⋮ Computing with Functions in Spherical and Polar Geometries II. The Disk ⋮ On principal components regression, random projections, and column subsampling ⋮ A multi-resolution approximation via linear projection for large spatial datasets

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