A randomized algorithm for the decomposition of matrices

DOI10.1016/j.acha.2010.02.003zbMath1210.65095OpenAlexW2057261601MaRDI QIDQ617703

Vladimir Rokhlin, Mark Tygert, Per-Gunnar Martinsson

Publication date: 13 January 2011

Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.acha.2010.02.003

zbMATH Keywords

singular value decomposition randomized algorithm Lanczos algorithm low rank approximation

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20)

Related Items

Algorithm 1022: Efficient Algorithms for Computing a Rank-Revealing UTV Factorization on Parallel Computing Architectures, Pass-efficient methods for compression of high-dimensional turbulent flow data, Fast Algorithms for Hyperspectral Diffuse Optical Tomography, Randomized Local Model Order Reduction, Randomized Complete Pivoting for Solving Symmetric Indefinite Linear Systems, Far-field compression for fast kernel summation methods in high dimensions, Nested Domain Decomposition with Polarized Traces for the 2D Helmholtz Equation, Modified truncated randomized singular value decomposition (MTRSVD) algorithms for large scale discrete ill-posed problems with general-form regularization, Randomized matrix-free trace and log-determinant estimators, Randomized generalized singular value decomposition, Randomized Quaternion Singular Value Decomposition for Low-Rank Matrix Approximation, Selecting Regularization Parameters for Nuclear Norm--Type Minimization Problems, Randomized QR with Column Pivoting, Fast Randomized Iteration: Diffusion Monte Carlo through the Lens of Numerical Linear Algebra, A fast direct boundary element method for 3D acoustic problems based on hierarchical matrices, A low-rank control variate for multilevel Monte Carlo simulation of high-dimensional uncertain systems, A hybrid stochastic interpolation and compression method for kernel matrices, Randomized LU decomposition, New fast divide-and-conquer algorithms for the symmetric tridiagonal eigenvalue problem, Randomized Quasi-Optimal Local Approximation Spaces in Time, Localized Model Reduction for Nonlinear Elliptic Partial Differential Equations: Localized Training, Partition of Unity, and Adaptive Enrichment, Sparsified randomization algorithms for low rank approximations and applications to integral equations and inhomogeneous random field simulation, A dynamical polynomial chaos approach for long-time evolution of SPDEs, Accelerated matrix completion algorithm using continuation strategy and randomized SVD, Practical Sketching Algorithms for Low-Rank Matrix Approximation, A fast solver for the narrow capture and narrow escape problems in the sphere, Multigrid with Rough Coefficients and Multiresolution Operator Decomposition from Hierarchical Information Games, A simple filter for detecting low-rank submatrices, Explicit deflation in Golub-Kahan-Lanczos bidiagonalization methods, A new fast direct solver for the boundary element method, The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection, Dense fast random projections and Lean Walsh transforms, Detecting low-rank clusters via random sampling, Literature survey on low rank approximation of matrices, A randomized singular value decomposition for third-order oriented tensors, Updating kernel methods in spectral decomposition by affinity perturbations, Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations, Fast structured LU factorization for nonsymmetric matrices, An \(O(N \log N)\) hierarchical random compression method for kernel matrices by sampling partial matrix entries, A geometric mapping cross approximation method, Bi-fidelity approximation for uncertainty quantification and sensitivity analysis of irradiated particle-laden turbulence, Randomized algorithms for the low multilinear rank approximations of tensors, Multidimensional butterfly factorization, Accurate and fast matrix factorization for low-rank learning., A randomized exponential canonical correlation analysis method for data analysis and dimensionality reduction, Randomized model order reduction, Generalized multiscale finite element methods for space-time heterogeneous parabolic equations, Householder QR Factorization With Randomization for Column Pivoting (HQRRP), Randomized algorithms for generalized Hermitian eigenvalue problems with application to computing Karhunen–Loève expansion, Compressing Rank-Structured Matrices via Randomized Sampling, Efficient methods for grouping vectors into low-rank clusters, Randomized LU decomposition using sparse projections, Fast randomized matrix and tensor interpolative decomposition using countsketch, Pass-Efficient Randomized Algorithms for Low-Rank Matrix Approximation Using Any Number of Views, A locally optimal rank revealing product decomposition, Practical error bounds for a non-intrusive bi-fidelity approach to parametric/stochastic model reduction, Randomized interpolative decomposition of separated representations, The method of polarized traces for the 2D Helmholtz equation, Geometric component analysis and its applications to data analysis, Stochastic boundary methods of fundamental solutions for solving PDEs, Tikhonov Regularization and Randomized GSVD, Randomized core reduction for discrete ill-posed problem, Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation, A Randomized Blocked Algorithm for Efficiently Computing Rank-revealing Factorizations of Matrices, Parallel Randomized and Matrix-Free Direct Solvers for Large Structured Dense Linear Systems, ASKIT: An Efficient, Parallel Library for High-Dimensional Kernel Summations, Randomized block Krylov methods for approximating extreme eigenvalues, Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning, Randomized algorithms for low-rank matrix factorizations: sharp performance bounds, Bi-fidelity reduced polynomial chaos expansion for uncertainty quantification

Uses Software

Algorithm 844

Cites Work