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

Zhang Bolong () and Mascagni Michael ()
Additional contact information
Zhang Bolong: Department of Computer Science, Florida State University, Tallahassee, FL 32306-4530, USA
Mascagni Michael: Department of Computer Science, Department of Mathematics, Department of Scientific Computing, Florida State University, Tallahassee, FL 32306-4530; and National Institute of Standards & Technology, Information Technology Laboratory, Applied and Computational Mathematics Division, Gaithersburg, MD 20899-8910, USA

Monte Carlo Methods and Applications, 2023, vol. 29, issue 3, 181-202

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 singular value decomposition (SVD) and column pivoting QR decomposition (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. Then we propose a novel randomized LU algorithm, called SubspaceLU, for the fixed low-rank approximation problem. SubspaceLU is based on the sketch of the co-range of input matrices and allows for an arbitrary number of passes of the input matrix, v ≥ 2 {v\geq 2} . Numerical experiments on CPU show that our proposed SubspaceLU is generally faster than the existing randomized LU decomposition, while remaining accurate. Experiments on GPU shows that our proposed SubspaceLU can gain more speedup than the existing randomized LU decomposition. We also propose a version of SubspaceLU, called SubspaceLU_FP, for the fixed precision low-rank matrix approximation problem. SubspaceLU_FP is a post-processing step based on an efficient blocked adaptive rank determination Algorithm 5 proposed in this paper. We present numerical experiments that show that SubspaceLU_FP can achieve close results to SVD but faster in speed. 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.

Keywords: Randomized numerical linear algebra; low-rank matrix approximation; randomized SVD; randomized LU (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1515/mcma-2023-2012 (text/html)
For access to full text, subscription to the journal or payment for the individual article is required.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bpj:mcmeap:v:29:y:2023:i:3:p:181-202:n:2

Ordering information: This journal article can be ordered from
https://www.degruyter.com/journal/key/mcma/html

DOI: 10.1515/mcma-2023-2012

Access Statistics for this article

Monte Carlo Methods and Applications is currently edited by Karl K. Sabelfeld

More articles in Monte Carlo Methods and Applications from De Gruyter
Bibliographic data for series maintained by Peter Golla ().