A Randomized Blocked Algorithm for Efficiently Computing Rank-revealing Factorizations of Matrices

DOI10.1137/15M1026080zbMath1352.65095arXiv1503.07157OpenAlexW2962760844WikidataQ114074336 ScholiaQ114074336MaRDI QIDQ2830627

Per-Gunnar Martinsson, Sergey Voronin

Publication date: 28 October 2016

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

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

zbMATH Keywords

singular value decompositionnumerical experimentsrandomized algorithmQR factorizationlow-rank approximationGram-Schmidt algorithm

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items

Pass-efficient methods for compression of high-dimensional turbulent flow data, Randomized numerical linear algebra: Foundations and algorithms, Randomized approaches to accelerate MCMC algorithms for Bayesian inverse problems, Randomized QLP decomposition, Selecting Regularization Parameters for Nuclear Norm--Type Minimization Problems, Efficient Randomized Algorithms for the Fixed-Precision Low-Rank Matrix Approximation, Pass-efficient randomized LU algorithms for computing low-rank matrix approximation, An efficient randomized fixed-precision algorithm for tensor singular value decomposition, The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection, Randomized Discrete Empirical Interpolation Method for Nonlinear Model Reduction, Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations, Householder QR Factorization With Randomization for Column Pivoting (HQRRP), Fast Hierarchical Solvers For Sparse Matrices Using Extended Sparsification and Low-Rank Approximation, Pass-Efficient Randomized Algorithms for Low-Rank Matrix Approximation Using Any Number of Views, Randomized Dynamic Mode Decomposition, Randomized block Krylov subspace methods for trace and log-determinant estimators, An efficient randomized algorithm for computing the approximate Tucker decomposition, Randomized GPU Algorithms for the Construction of Hierarchical Matrices from Matrix-Vector Operations, A Randomized Blocked Algorithm for Efficiently Computing Rank-revealing Factorizations of Matrices, Robust and Accurate Stopping Criteria for Adaptive Randomized Sampling in Matrix-Free Hierarchically Semiseparable Construction, Efficient Algorithms for Eigensystem Realization Using Randomized SVD, A Block Bidiagonalization Method for Fixed-Accuracy Low-Rank Matrix Approximation, Randomized Algorithms for Low-Rank Tensor Decompositions in the Tucker Format

Uses Software

• ATLAS

Cites Work

• Unnamed Item
• Unnamed Item
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• A randomized algorithm for the decomposition of matrices
• Numerics of Gram-Schmidt orthogonalization
• A DEIM Induced CUR Factorization
• A Randomized Blocked Algorithm for Efficiently Computing Rank-revealing Factorizations of Matrices
• Communication-optimal Parallel and Sequential QR and LU Factorizations
• A Randomized Algorithm for Principal Component Analysis
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
• On the Compression of Low Rank Matrices