Subspaces analysis for random projection UTV framework. (English) Zbl 1508.65035
Summary: The UTV decompositions are promising and computationally efficient alternatives to the singular value decomposition (SVD), which can provide high-quality information about rank, range, and nullspace. However, for large-scale matrices, we want more computationally efficient algorithms. Recently, randomized algorithms with their surprising reliability and computational efficiency have become increasingly popular in many application areas. In this paper, we analyze the subspace properties of a random projection UTV framework and give the bounds of subspace distances between the exact and the approximate singular subspaces, the approximate methods including random projection ULV, random projection URV, and random projection SVD. Numerical experiments demonstrate the effectiveness of the proposed bounds.
MSC:
| 65F20 | Numerical solutions to overdetermined systems, pseudoinverses |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
| 65F25 | Orthogonalization in numerical linear algebra |
References:
| [1] | C. Boutsidis, M. W. Mahoney, and P. Drineas, An improved approximation algorithm for the column subset selection problem, in Proceedings of the 2009 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009, pp. 968-977, https://doi.org/10.1137/1.9781611973068.105. · Zbl 1420.68235 |
| [2] | C. Boutsidis and D. P. Woodruff, Optimal CUR matrix decompositions, SIAM J. Comput., 46 (2017), pp. 543-589. · Zbl 1359.65059 |
| [3] | T. F. Chan, Rank revealing QR factorizations, Linear Algebra Appl., 88 (1987), pp. 67-82. · Zbl 0624.65025 |
| [4] | P. Drineas and M. W. Mahoney, RandNLA: Randomized numerical linear algebra, Comm. ACM, 59 (2016), pp. 80-90. |
| [5] | J. A. Duersch and M. Gu, Randomized QR with column pivoting, SIAM J. Sci. Comput., 39 (2017), pp. C263-C291. · Zbl 1371.65026 |
| [6] | C. Eckart and G. Young, The approximation of one matrix by another of lower rank, Psychometrika, 1 (1936), pp. 211-218. · JFM 62.1075.02 |
| [7] | N. B. Erichson, S. Voronin, S. L. Brunton, and J. N. Kutz, Randomized Matrix Decompositions Using R, preprint, arXiv:1608.02148, 2016. |
| [8] | R. Fierro and P. Hansen, Low-rank revealing UTV decompositions, Numer. Algorithms, 15 (1997), pp. 37-55. · Zbl 0887.65043 |
| [9] | R. D. Fierro and J. R. Bunch, Bounding the subspaces from rank revealing two-sided orthogonal decompositions, SIAM J. Matrix Anal. Appl., 16 (1995), pp. 743-759. · Zbl 0831.65044 |
| [10] | R. D. Fierro, P. C. Hansen, and P. S. K. Hansen, UTV tools: MATLAB templates for rank-revealing UTV decompositions, Numer. Algorithms, 20 (1999), pp. 165-194. · Zbl 0936.65054 |
| [11] | G. H. Golub and C. F. V. Loan, Matrix Computations, 4th ed., Johns Hopkins University Press, Baltimore, 2013. · Zbl 1268.65037 |
| [12] | M. Gu, Subspace iteration randomization and singular value problems, SIAM J. Sci. Comput., 37 (2015), pp. A1139-A1173. · Zbl 1328.65088 |
| [13] | N. Halko, P. G. Martinsson, and J. A. Tropp, Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, SIAM Rev., 53 (2011), pp. 217-288. · Zbl 1269.65043 |
| [14] | R. A. Horn and C. R. Johnson, Matrix Analysis, 2nd ed., Cambridge University Press, Cambridge, 2013. · Zbl 1267.15001 |
| [15] | E. Liberty, F. Woolfe, P. G. Martinsson, V. Rokhlin, and M. Tygert, Randomized algorithms for the low-rank approximation of matrices, Proc. Natl. Acad. Sci., 104 (2007), pp. 20167-20172. · Zbl 1215.65080 |
| [16] | M. W. Mahoney, Randomized Algorithms for Matrices and Data, preprint, arXiv:1104.5557, 2011. · Zbl 1232.68173 |
| [17] | G. Ming and S. Eisenstat, Efficient algorithms for computing a strong rank-revealing QR factorization, SIAM J. Sci. Comput., 17 (1996), pp. 848-869. · Zbl 0858.65044 |
| [18] | V. Rokhlin, A. Szlam, and M. Tygert, A randomized algorithm for principal component analysis, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 1100-1124. · Zbl 1198.65035 |
| [19] | G. W. Stewart, Updating a rank-revealing ULV decomposition, SIAM J. Matrix Anal. Appl., 14 (1993), pp. 494-499. · Zbl 0771.65021 |
| [20] | G. W. Stewart, Matrix Algorithms, Volume 1: Basic Decompositions, SIAM, Philadelphia, 1998. · Zbl 0910.65012 |
| [21] | G. W. Stewart, Four algorithms for the efficient computation of truncated pivoted QR approximations to a sparse matrix, Numer. Math., 83 (1999), pp. 313-323. · Zbl 0957.65031 |
| [22] | G. W. Stewart, The QLP approximation to the singular value decomposition, SIAM J. Sci. Comput., 20 (1999), pp. 1336-1348. · Zbl 0939.65062 |
| [23] | J. A. Tropp, A. Yurtsever, M. Udell, and V. Cevher, Practical sketching algorithms for low-rank matrix approximation, SIAM J. Matrix Anal. Appl., 38 (2017), pp. 1454-1485. · Zbl 1379.65026 |
| [24] | S. Voronin and P. G. Martinsson, RSVDPACK: An Implementation of Randomized Algorithms for Computing the Singular Value, Interpolative, and CUR Decompositions of Matrices on Multi-Core and GPU Architectures, preprint, arXiv:1502.05366, 2015. |
| [25] | N. Wu and H. Xiang, Randomized QLP decomposition, Linear Algebra Appl., 599 (2020), pp. 18-35. · Zbl 1439.65060 |
| [26] | H. Xiang and J. Zou, Regularization with randomized SVD for large-scale discrete inverse problems, Inverse Problems, 29 (2013), 085008. · Zbl 1286.65053 |
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.
