Randomized Generalized Singular Value Decomposition

doi:10.1007/s42967-020-00061-x

Communications on Applied Mathematics and Computation ›› 2021, Vol. 3 ›› Issue (1): 137-156.doi: 10.1007/s42967-020-00061-x

• ORIGINAL PAPER • Previous Articles

Randomized Generalized Singular Value Decomposition

Wei Wei¹, Hui Zhang^1,2, Xi Yang¹, Xiaoping Chen³

1 College of Science, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China;
2 College of Jincheng, Nanjing University of Aeronautics and Astronautics, Nanjing 211156, China;
3 Department of Mathematics, Taizhou University, Taizhou 225300, Zhejiang Province, China

Received:2019-09-30 Revised:2020-01-21 Published:2021-03-15
Contact: Xiaoping Chen, cxpnuaa@163.com;Wei Wei, w.wei@nuaa.edu.cn;Hui Zhang, zh1990@nuaa.edu.cn;Xi Yang, yangxi@nuaa.edu.cn,yangxi@lsec.ac.cn E-mail:cxpnuaa@163.com;w.wei@nuaa.edu.cn;zh1990@nuaa.edu.cn;yangxi@nuaa.edu.cn,yangxi@lsec.ac.cn
Supported by:
The research is supported by the National Natural Science Foundation of China under Grant nos. 11701409 and 11571171, the Natural Science Foundation of Jiangsu Province of China under Grant BK20170591 and the Natural Science Foundation of Jiangsu Higher Education Institutions of China under Grant 17KJB110018.

Abstract

Abstract: The generalized singular value decomposition (GSVD) of two matrices with the same number of columns is a very useful tool in many practical applications. However, the GSVD may suffer from heavy computational time and memory requirement when the scale of the matrices is quite large. In this paper, we use random projections to capture the most of the action of the matrices and propose randomized algorithms for computing a low-rank approximation of the GSVD. Serval error bounds of the approximation are also presented for the proposed randomized algorithms. Finally, some experimental results show that the proposed randomized algorithms can achieve a good accuracy with less computational cost and storage requirement.

Key words: Generalized singular value decomposition, Randomized algorithm, Low-rank approximation, Error analysis

CLC Number:

Wei Wei, Hui Zhang, Xi Yang, Xiaoping Chen. Randomized Generalized Singular Value Decomposition[J]. Communications on Applied Mathematics and Computation, 2021, 3(1): 137-156.

TrendMD

References

1. Bai, Z.J., Demmel, J.W.: Computing the generalized singular value decomposition. SIAM J. Sci. Comput. 14(6), 1464–1486 (1993)
2. Boutsidis, C., Drineas, P.: Random projections for the nonnegative least-squares problem. Linear Algebra Appl. 431(5), 760–771 (2008)
3. Cheng, H., Gimbutas, Z., Martinsson, P.G., Rokhlin, V.: On the compression of low rank matrices. SIAM J. Sci. Comput. 26(4), 1389–1404 (2005)
4. Chu, M.T., Funderlic, R.E., Golub, G.H.: On a variational formulation of the generalized singular value decomposition. SIAM J. Matrix Anal. Appl. 18(4), 1082–1092 (1997)
5. Drineas, P., Mahoney, M.W.: On the Nystro?m method for approximating a Gram matrix for improved kernel-based learning. J. Mach. Learn. Res. 6, 2153–2175 (2005)
6. Drineas, P., Mahoney, M.W., Muthukrishnan, S.: Relative-error CUR matrix decomposition. SIAM J. Matrix Anal. Appl. 30(2), 844–881 (2008)
7. Feng, G.Y., Hu, D.W., Zhou, Z.T.: A direct locality preserving projections (DLPP) algorithm for image recognition. Neural Process. Lett. 27(3), 247–255 (2008)
8. Halko, N., Martinsson, P.G., Tropp, J.A.: Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev. 53(2), 217–288 (2011)
9. He, X.F., Yan, S.C., Hu, Y.X., Niyogi, P., Zhang, H.J.: Face recognition using Laplacian faces. IEEE Trans. Pattern Anal. Mach. Intell. 27(3), 328–340 (2005)
10. Li, R.C.: Bounds on perturbations of generalized singular values and of associated subspaces. SIAM J. Matrix Anal. Appl. 14(1), 195–234 (1993)
11. Liberty, E., Woolfe, F., Martinsson, P.G., Rokhlin, V., Tygert, M.: Randomized algorithms for the lowrank approximation of matrices. Proc. Natl. Acad. Sci. USA 104(51), 20167–20172 (2007)
12. Mahoney, M.W.: Randomized algorithms for matrices and data. Found. Trends Mach. Learn. 3(2), 123–224 (2010)
13. Martinsson, P.G., Rokhlin, V., Tygert, M.: A randomized algorithm for the decomposition of matrices. Appl. Comput. Harmon. Anal. 30(1), 47–68 (2011)
14. Mirsky, L.: Symmetric gauge functions and unitarily invariant norms. Q. J. Math. 11(1), 50–59 (1960)
15. Paige, C.C., Saunders, M.A.: Towards a generalized singular value decomposition. SIAM J. Numer. Anal. 18(3), 398–405 (1981)
16. Rachkovskij, D.A., Revunova, E.G.: A randomized method for solving discrete ill-posed problems. Cybern. Syst. Anal. 48(4), 621–635 (2012)
17. Rokhlin, V., Tygert, M.: A fast randomized algorithm for overdetermined linear least-squares regression. Proc. Natl. Acad. Sci. USA 105(36), 13212–13217 (2008)
18. Rokhlin, V., Szlam, A., Tygert, M.: A randomized algorithm for principle component analysis. SIAM J. Matrix Anal. Appl. 31(3), 1100–1124 (2010)
19. Saibaba, A.K., Lee, J., Kitanidis, P.K.: Randomized algorithms for generalized Hermitian eigenvalue problems with application to computing Karhunen–Loe? ve expansion. Numer. Linear Algebra Appl. 23(2), 314–339 (2016)
20. Shabat, G., Shmueli, Y., Aizenbud, Y., Averbuch, A.: Randomized LU decomposition. Appl. Comput. Harmon. Anal. 44(2), 246–272 (2018)
21. Stewart, G.W.: Computing the CS-decomposition of a partitioned orthonormal matrix. Numer. Math. 40(3), 297–306 (1982)
22. Sun, J.G.: Perturbation analysis for the generalized singular value problem. SIAM J. Numer. Anal. 20(3), 611–625 (1983)
23. Van Loan, C.F.: Generalizing the singular value decomposition. SIAM J. Numer. Anal. 13(1), 76–83 (1976)
24. Van Loan, C.F.: Computing the CS and the generalized singular value decomposition. Numer. Math. 46(4), 479–491 (1985)
25. Wei, Y.M., Xie, P.P., Zhang, L.P.: Tikhonov regularization and randomized GSVD. SIAM J. Matrix Anal. Appl. 37(2), 649–675 (2016)
26. Woolfe, F., Liberty, E., Rokhlin, V., Tygert, M.: A fast randomized algorithm for the approximation of matrices. Appl. Comput. Harmon. Anal. 25(3), 335–366 (2008)
27. Xiang, H., Zou, J.: Regularization with randomized SVD for large-scale discrete inverse problems. Inverse Prob. 29(8), 085008 (2013)
28. Xiang, H., Zou, J.: Randomized algorithms for large-scale inverse problems with general Tikhonov regularizations. Inverse Prob. 31(8), 085008 (2015)

[1]	Kailiang Wu, Dongbin Xiu. Sequential Approximation of Functions in Sobolev Spaces Using Random Samples [J]. Communications on Applied Mathematics and Computation, 2019, 1(3): 449-466.
[2]	Xuhong Yu, Zhongqing Wang, Huiyuan Li. Jacobi-Sobolev Orthogonal Polynomials and Spectral Methods for Elliptic Boundary Value Problems [J]. Communications on Applied Mathematics and Computation, 2019, 1(2): 283-308.

Randomized Generalized Singular Value Decomposition

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 2

Recommended Articles

Metrics

Comments