Pass-efficient randomized LU algorithms for computing low-rank matrix approximation

DOI10.1515/MCMA-2023-2012MaRDI QIDQ6073724zbMATH OpenOpenAlexFDO

Authors Bolong Zhang, Michael Mascagni

Publication date 18 September 2023

Published in Monte Carlo Methods and Applications (Search for Journal in Brave)

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

zbMATH Keywords

low-rank matrix approximationrandomized SVDrandomized numerical linear algebrarandomized LU

Mathematics Subject Classification ID

Probabilistic methods, stochastic differential equations (65C99) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Abstract: Low-rank matrix approximation is extremely useful in the analysis of data that arises in scientific computing, engineering applications, and data science. However, as data sizes grow, traditional low-rank matrix approximation methods, such as SVD and CPQR, are either prohibitively expensive or cannot provide sufficiently accurate results. A solution is to use randomized low-rank matrix approximation methods such as randomized SVD , and randomized LU decomposition on extremely large data sets. In this paper, we focus on the randomized LU decomposition method. First, we employ a reorthogonalization procedure to perform the power iteration of the existing randomized LU algorithm to compensate for the rounding errors caused by the power method. Then we propose a novel randomized LU algorithm, called PowerLU, for the fixed low-rank approximation problem. PowerLU allows for an arbitrary number of passes of the input matrix, $vgeq2$. Recall that the existing randomized LU decomposition only allows an even number of passes. We prove the theoretical relationship between PowerLU and the existing randomized LU. Numerical experiments show that our proposed PowerLU is generally faster than the existing randomized LU decomposition, while remaining accurate. We also propose a version of PowerLU, called PowerLU_FP, for the fixed precision low-rank matrix approximation problem. PowerLU_FP is based on an efficient blocked adaptive rank determination Algorithm 4.1 proposed in this paper. We present numerical experiments that show that PowerLU_FP can achieve almost the same accuracy and is faster than the randomized blocked QB algorithm by Martinsson and Voronin. We finally propose a single-pass algorithm based on LU factorization. Tests show that the accuracy of our single-pass algorithm is comparable with the existing single-pass algorithms.

Recommendations

• Pass-efficient randomized algorithms for low-rank matrix approximation using any number of views
• Efficient randomized algorithms for the fixed-precision low-rank matrix approximation
• Single-pass randomized algorithms for LU decomposition
• Randomized LU decomposition
• Single-pass randomized QLP decomposition for low-rank approximation

Cites work

• A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices
• Algorithm 971
• CUR matrix decompositions for improved data analysis
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
• Efficient randomized algorithms for the fixed-precision low-rank matrix approximation
• Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
• Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
• Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Lectures on randomized numerical linear algebra
• On the existence and computation of rank-revealing LU factorizations
• Pass-efficient randomized algorithms for low-rank matrix approximation using any number of views
• Practical sketching algorithms for low-rank matrix approximation
• Randomized Algorithms for Matrices and Data
• Randomized LU decomposition
• Randomized algorithms in numerical linear algebra
• Single-pass randomized algorithms for LU decomposition
• Sparsified randomization algorithms for low rank approximations and applications to integral equations and inhomogeneous random field simulation
• Strong rank revealing LU factorizations
• Tensor Decompositions and Applications
• Tensor-train decomposition
• The QLP Approximation to the Singular Value Decomposition
• Updating a Rank-Revealing ULV Decomposition
• Why Are Big Data Matrices Approximately Low Rank?

Cited in

(2)

• Low Rank Approximation of a Sparse Matrix Based on LU Factorization with Column and Row Tournament Pivoting
• Pass-efficient truncated UTV for low-rank approximations

This page was built for publication: Pass-efficient randomized LU algorithms for computing low-rank matrix approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6073724)