×

Single-pass randomized algorithms for LU decomposition. (English) Zbl 1434.15012

Summary: In this paper, we present some single-pass randomized algorithms to compute LU decomposition. These algorithms need only one pass over the original matrix and hence are very suitable for extremely large and high-dimensional matrix stored outside of core memory or generated in a streaming fashion. Rigorous error bounds and complexity of these algorithms are provided. Numerical experiments show that these single-pass algorithms have the similar accuracy and runtime (excluding the cost of matrix transfer) compared with the state-of-the-art randomized algorithms for LU decomposition.

MSC:

15A23 Factorization of matrices
68W20 Randomized algorithms

Software:

mctoolbox
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aizenbud, Y.; Shabat, G.; Averbuch, A., Randomized LU decomposition using sparse projections, Comput. Math. Appl., 72, 9, 2525-2534 (2016) · Zbl 1368.65068
[2] Anderson, D.; Gu, M., An efficient, sparsity-preserving, online algorithm for low-rank approximation, (ICML Proc., vol. 70 (2017)), 156-165
[3] Bajaj, C.; Wang, Y.; Wang, T. M., SketchyCoreSVD: sketchySVD from random subsampling of the data matrix (2019)
[4] Bjarkason, E. K., Pass-efficient randomized algorithms for low-rank matrix approximation using any number of views, SIAM J. Sci. Comput., 41, 4, A2355-A2383 (2019) · Zbl 1437.65029
[5] Gu, M., Subspace iteration randomization and singular value problems, SIAM J. Sci. Comput., 37, 3, A1139-A1173 (2015) · Zbl 1328.65088
[6] Golub, G. H.; Van Loan, C. F., Matrix Computations (2012), The Johns Hopkins University Press: The Johns Hopkins University Press Baltimore
[7] Halko, N.; Martinsson, P. G.; Tropp, J. A., Finding structure with randomness: probabilities algorithms for constructing approximate matrix decompositions, SIAM Rev., 53, 2, 217-288 (2011) · Zbl 1269.65043
[8] Higham, N. J., Accuracy and Stability of Numerical Algorithms (2002), SIAM: SIAM Philadelphia · Zbl 1011.65010
[9] Kaloorazi, M. F.; de Lamare, R. C., Subspace-orbit randomized decomposition for low-rank matrix approximations, IEEE Trans. Signal Process., 66, 16, 4409-4424 (2018) · Zbl 1414.68143
[10] Litvak, A. E.; Pajor, A.; Rudelson, M.; Tomczak-Jaegermann, N., Smallest singular value of random matrices and geometry of random polytopes, Adv. Math., 195, 2, 491-523 (2005) · Zbl 1077.15021
[11] Litvak, A. E.; Rivasplata, O., Smallest singular value of sparse random matrices, Stud. Math., 212, 3, 195-218 (2012) · Zbl 1277.60016
[12] Miranian, L.; Gu, M., Strong rank revealing LU factorizations, Linear Algebra Appl., 367, 1-16 (2003) · Zbl 1020.65016
[13] Pan, C. T., On the existence and computation of rank-revealing LU factorizations, Linear Algebra Appl., 316, 1-3, 199-222 (2000) · Zbl 0962.65023
[14] Shabat, G.; Shmueli, Y.; Aizenbud, Y.; Averbuch, A., Randomized LU decomposition, Appl. Comput. Harmon. Anal., 44, 2, 246-272 (2018) · Zbl 1380.65077
[15] Tropp, J. A.; Yurtsever, A.; Udell, M.; Cevher, V., Practical sketching algorithms for low-rank matrix approximation, SIAM J. Matrix Anal. Appl., 38, 4, 1454-1485 (2017) · Zbl 1379.65026
[16] Tropp, J. A.; Yurtsever, A.; Udell, M.; Cevher, V., More practical skeching algorithms for low-rank matrix approximation (2018), Technical Report No. 2018-01
[17] Tropp, J. A.; Yurtsever, A.; Udell, M.; Cevher, V., Streaming low-rank matrix approximation with an application to scientific simulation, SIAM J. Sci. Comput., 41, 4, A2430-A2463 (2019) · Zbl 1420.65060
[18] Woodruff, D. P., Sketching as a tool for numerical linear algebra, Found. Trends Theor. Comput. Sci., 10, 1-2, 1-157 (2014) · Zbl 1316.65046
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.