An alternating direction power-method for computing the largest singular value and singular vectors of a matrix

Yonghong Duan; Ruiping Wen; Yonghong Duan; Ruiping Wen

doi:10.3934/math.2023056

AIMS Mathematics

2023, Volume 8, Issue 1: 1127-1138. doi: 10.3934/math.2023056

Previous Article Next Article

Research article

An alternating direction power-method for computing the largest singular value and singular vectors of a matrix

Yonghong Duan ¹,
Ruiping Wen ^{2
,
,}

1.
Department of Applied Mathematics, Taiyuan University, Taiyuan 030032, Shanxi, China
2.
Key Laboratory for Engineering and Computing Science, Shanxi Provincial Department of Education, Taiyuan Normal University, Jinzhong 030619, Shanxi, China

Received: 21 July 2022 Revised: 10 October 2022 Accepted: 11 October 2022 Published: 17 October 2022
MSC : 65F10, 65F15

The singular value decomposition (SVD) is an important tool in matrix theory and numerical linear algebra. Research on the efficient numerical algorithms for computing the SVD of a matrix is extensive in the past decades. In this paper, we propose an alternating direction power-method for computing the largest singular value and singular vector of a matrix. The new method is similar to the well-known power method but needs fewer operations in the iterations. Convergence of the new method is proved under suitable conditions. Theoretical analysis and numerical experiments show both that the new method is feasible and is effective than the power method in some cases.
- singular value decomposition (SVD),
- power method,
- alternating direction implicit (ADI),
- singular value,
- singular vector,
- convergence
Citation: Yonghong Duan, Ruiping Wen. An alternating direction power-method for computing the largest singular value and singular vectors of a matrix[J]. AIMS Mathematics, 2023, 8(1): 1127-1138. doi: 10.3934/math.2023056

Related Papers:

Abstract

The singular value decomposition (SVD) is an important tool in matrix theory and numerical linear algebra. Research on the efficient numerical algorithms for computing the SVD of a matrix is extensive in the past decades. In this paper, we propose an alternating direction power-method for computing the largest singular value and singular vector of a matrix. The new method is similar to the well-known power method but needs fewer operations in the iterations. Convergence of the new method is proved under suitable conditions. Theoretical analysis and numerical experiments show both that the new method is feasible and is effective than the power method in some cases.

References

[1]	J. Demmel, Applied numerical linear algebra, Philadelphia: SIAM, 1997. https://doi.org/10.1137/1.9781611971446
[2]	G. H. Golub, C. F. Van Loan, Matrix computations, 4 Eds., Baltimore and London: The Johns Hopkins University Press, 2013.
[3]	J. F. Cai, E. J. Candès, Z. Shen, A singular value thresholding algorithm for matrix completion, SIAM J. Optim., 20 (2010), 1956–1982. https://doi.org/10.1137/080738970 doi: 10.1137/080738970
[4]	L. L. Scharf, The SVD and reduced rank signal processing, Signal Process., 25 (1991), 113–133. https://doi.org/10.1016/0165-1684(91)90058-Q doi: 10.1016/0165-1684(91)90058-Q
[5]	B. D. Moor, The singular value decomposition and long and short spaces of noisy matrices, IEEE Trans. Signal Proc., 41 (1993), 2826–2838. https://doi.org/10.1109/78.236505 doi: 10.1109/78.236505
[6]	M. V. Kulikova, Hyperbolic SVD-based Kalman filtering for Chandrasekhar recursion, IET Control Theory Appl., 13 (2019), 1525. https://doi.org/10.1049/iet-cta.2018.5864 doi: 10.1049/iet-cta.2018.5864
[7]	G. H. Golub, W. Kahan, Calculating the singular values and the pesudo-inverse of a matrix, SIAM J. Numer. Anal., 2 (1965), 205–224. https://doi.org/10.1137/0702016 doi: 10.1137/0702016
[8]	M. Gu, S. C. Eisenstat, A divide-and-conquer algorithm for the bidiagonal SVD, SIAM J. Matrix Anal. Appl., 16 (1995), 79–92. https://doi.org/10.1137/S0895479892242232 doi: 10.1137/S0895479892242232
[9]	Z. Drmac, K. Veselic, New fast and accurate Jacobi SVD algorithm, SIAM J. Matrix Anal. Appl., 29 (2008), 1322–1362. https://doi.org/10.1137/050639193 doi: 10.1137/050639193
[10]	H. Zha, A note on the existence of the hyperbolic singular value decomposition, Linear Algebra Appl., 240 (1996), 199–205. https://doi.org/10.1016/0024-3795(94)00197-9 doi: 10.1016/0024-3795(94)00197-9
[11]	A. W. Bojanczyk, An implicit Jacobi-like method for computing generalized hyperbolic SVD, Linear Algebra Appl., 358 (2003), 293–307. https://doi.org/10.1016/S0024-3795(02)00394-4 doi: 10.1016/S0024-3795(02)00394-4
[12]	D. S. Shirokov, A note on the hyperbolic singular value decomposition without hyperexchange matrices, J. Comput. Appl. Math., 2021, 1–8.
[13]	V. Novaković, S. Singer, A GPU-based hyperbolic SVD algorithm, BIT Numer. Math., 51 (2011), 1009–1030. https://doi.org/10.1007/s10543-011-0333-5 doi: 10.1007/s10543-011-0333-5
[14]	J. Huang, Z. Jia, A cross-product free Jacobi-Davidson type method for computing a partial generalized singular value decomposition (GSVD) of a large matrix pair, 2020, 1–14.
[15]	J. Demmel, P. Koev, Accurate SVDs of weakly diagonally dominant M-matrices, Numer. Math., 98 (2004), 99–104. https://doi.org/10.1007/s00211-004-0527-8 doi: 10.1007/s00211-004-0527-8
[16]	J. Demmel, P. Koev, Accurate SVDs of polynomial Vandermonde matrices involving orthonormal polynomials, Linear Algebra Appl., 417 (2006), 382–396. https://doi.org/10.1016/j.laa.2005.09.014 doi: 10.1016/j.laa.2005.09.014
[17]	J. Demmel, W. Kahan, Accurate singular values of bidiagonal matrices, SIAM J. Stat. Comp., 11 (1990), 873–912. https://doi.org/10.1137/0911052 doi: 10.1137/0911052
[18]	J. Demmel, Accurate singular value decompositions of structured matrices, SIAM J. Matrix Anal. Appl., 21 (1999), 562–580. https://doi.org/10.1137/S0895479897328716 doi: 10.1137/S0895479897328716
[19]	F. M. Dopico, J. Moro, A note on multiplicative backward errors of accurate SVD algorithms, SIAM J. Matrix Anal. Appl., 25 (2004), 1021–1031. https://doi.org/10.1137/S0895479803427005 doi: 10.1137/S0895479803427005
[20]	R. Escalante, M. Raydan, Alternating projection methods, Philadelphia: SIAM, 2007.
[21]	V. Fernando, B. N. Parlett, Accurate singular values and differential qd algorithms, Numer. Math., 67 (1994), 191–229. https://doi.org/10.1007/s002110050024 doi: 10.1007/s002110050024
[22]	B. Grosser, B. Lang, An $O(n^2)$ algorithm for the bidiagonal SVD, Linear Algebra Appl., 358 (2003), 45–70. https://doi.org/10.1016/S0024-3795(01)00398-6 doi: 10.1016/S0024-3795(01)00398-6
[23]	R. A. Horn, C. R. Johnson, Matrix analysis, Cambridge: Cambridge University Press, 1985. https://doi.org/10.1017/CBO9780511810817
[24]	N. J. Higham, QR factorization with complete pivoting and accurate computation of the SVD, Linear Algebra Appl., 309 (2000), 153–174. https://doi.org/10.1016/S0024-3795(99)00230-X doi: 10.1016/S0024-3795(99)00230-X
[25]	P. Koev, Accurate eigenvalues and SVDs of totally nonnegative matrices, SIAM J. Matrix Anal. Appl., 27 (2005), 1–23. https://doi.org/10.1137/S0895479803438225 doi: 10.1137/S0895479803438225
[26]	Q. Ye, Computing singular values of diagonally dominant matrices to high relative accuracy, Math. Comput., 77 (2008), 2195–2230. https://doi.org/10.1090/S0025-5718-08-02112-1 doi: 10.1090/S0025-5718-08-02112-1
[27]	J. Blanchard, J. Tanner, K. Wei, CGIHT: Conjugate grandient iterative hard thresholding for compressed sensing and matrix completion, University of Oxford, 2014. https://doi.org/10.1093/imaiai/iav011
[28]	M. Hardt, E. Price, The noisy power method: A meta algorithm with applications, International Conference on Neural Information Processing Systems MIT Press, 2014.
[29]	J. Nocedal, S. Wright, Numerical optimization, Berlin: Springer, 2006.
[30]	T. Davis, Y. Hu, The University of Florida sparse matrix collection, ACM Trans. Math. Software, 38 (2011), 1–25. https://doi.org/10.1145/2049662.2049663 doi: 10.1145/2049662.2049663

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)