×

Newton’s method for the parameterized generalized eigenvalue problem with nonsquare matrix pencils. (English) Zbl 1465.65029

Summary: The \(l\) parameterized generalized eigenvalue problems for the nonsquare matrix pencils, proposed by D. Chu and G. H. Golub [SIAM J. Matrix Anal. Appl. 28, No. 3, 770–787 (2006; Zbl 1128.15004)], can be formulated as an optimization problem on a corresponding complex product Stiefel manifold. In this paper, an effective and efficient algorithm based on the Riemannian Newton’s method is established to solve the underlying problem. Under our proposed framework, to solve the corresponding Newton’s equation, it can be converted to solve a standard real symmetric linear system with a dimension reduction. By combining the Riemannian curvilinear search method with Barzilai-Borwein steps, a hybrid algorithm with both global and quadratic convergence is obtained. Numerical experiments are provided to illustrate the efficiency of the proposed method. Detailed comparisons with some latest methods are also provided to show the merits of the proposed approach.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A18 Eigenvalues, singular values, and eigenvectors

Citations:

Zbl 1128.15004

Software:

Manopt
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Absil, PA; Baker, C.; Gallivan, K., A truncated-CG style method for symmetric generalized eigenvalue problems[J], J. Comput. Appl. Math., 189, 1-2, 274-285 (2006) · Zbl 1090.65042 · doi:10.1016/j.cam.2005.10.006
[2] Boutry, G.; Elad, M.; Golub, GH; Milanfar, P., The generalized eigenvalue problem for nonsquare pencils using a minimal perturbation approach[J], SIAM J. Matrix Anal. Appl., 27, 2, 582-601 (2005) · Zbl 1100.65035 · doi:10.1137/S0895479803428795
[3] Chu, D.; Golub, GH, On a generalized eigenvalue problem for nonsquare pencils[J], SIAM J. Matrix Anal. Appl., 28, 3, 770-787 (2006) · Zbl 1128.15004 · doi:10.1137/050628258
[4] Kressner, D.; Mengi, E.; Nakić, I.; Truhar, N., Generalized eigenvalue problems with specified eigenvalues[J], IMA J. Numer. Anal., 34, 2, 480-501 (2014) · Zbl 1288.65051 · doi:10.1093/imanum/drt021
[5] Lecumberri, P.; Gómez, M.; Carlosena, A., Generalized eigenvalues of nonsquare pencils with structure[J], SIAM J. Matrix Anal. Appl., 30, 1, 41-55 (2008) · Zbl 1158.15005 · doi:10.1137/060669267
[6] Ito, S.; Murota, K., An algorithm for the generalized eigenvalue problem for nonsquare matrix pencils by minimal perturbation approach[J], SIAM J. Matrix Anal. Appl., 37, 1, 409-419 (2016) · Zbl 1376.65050 · doi:10.1137/14099231X
[7] Zheng, H.; Liu, L., The sign-based methods for solving a class of nonlinear complementarity problems[J], J. Optim. Theory Appl., 180, 2, 480-499 (2019) · Zbl 1416.90052 · doi:10.1007/s10957-018-1361-y
[8] Golub, GH; Loan, CFV, An analysis of the total least squares problem[J], SIAM J. Numer. Anal., 17, 6, 883-893 (1980) · Zbl 0468.65011 · doi:10.1137/0717073
[9] Li, JF; Li, W.; Vong, SW; Luo, QL; Xiao, M., A Riemannian optimization approach for solving the generalized eigenvalue problem for nonsquare matrix pencils[J], J. Sci. Comput., 82, 3, 1-43 (2020) · Zbl 1434.65267 · doi:10.1007/s10915-019-01102-1
[10] Sato, H.; Iwai, T., A Riemannian optimization approach to the matrix singular value decomposition[J], SIAM J. Optim., 23, 1, 188-212 (2013) · Zbl 1267.65070 · doi:10.1137/120872887
[11] Sato, H., Iwai, T.: A complex singular value decomposition algorithm based on the Riemannian Newton method[C]. In: 52nd IEEE Conference on Decision and Control, pp. 2972-2978. IEEE (2013)
[12] Sato, H.: Riemannian conjugate gradient method for complex singular value decomposition problem[C]. In: 53rd IEEE Conference on Decision and Control, pp. 5849-5854. IEEE (2014)
[13] Aihara, K.; Sato, H., A matrix-free implementation of Riemannian Newton’s method on the Stiefel manifold[J], Optim. Lett., 11, 8, 1729-1741 (2017) · Zbl 1386.90141 · doi:10.1007/s11590-016-1090-9
[14] Sato, H., Riemannian Newton-type methods for joint diagonalization on the Stiefel manifold with application to independent component analysis[J], Optimization, 66, 12, 2211-2231 (2017) · Zbl 1386.90176 · doi:10.1080/02331934.2017.1359592
[15] Li, J.F., Wen, Y.Q., Zhou, X.L., Wang, K.: Effective algorithms for solving trace minimization problem in multivariate statistics[J]. Mathematical Problems in Engineering, 2020, 2020:Article ID 3054764 · Zbl 1459.65005
[16] Wen, Z.; Yin, W., A feasible method for optimization with orthogonality constraints[J], Math. Program., 142, 1-2, 397-434 (2013) · Zbl 1281.49030 · doi:10.1007/s10107-012-0584-1
[17] Hu, J.; Liu, X.; Wen, ZW; Yuan, YX, A brief introduction to manifold optimization[J], J. Oper. Res. Soc. China, 8, 2, 199-248 (2020) · Zbl 1474.49093 · doi:10.1007/s40305-020-00295-9
[18] Henderson, HV; Searle, SR, The vec-permutation matrix, the vec operator and Kronecker products: A review[J], Linear Multilinear Algebra, 9, 4, 271-288 (1981) · Zbl 0458.15006 · doi:10.1080/03081088108817379
[19] Yuan, S.; Liao, A.; Lei, Y., Least squares Hermitian solution of the matrix equation (AXB,CXD) = (E,F) with the least norm over the skew field of quaternions[J], Math. Comput. Model., 48, 1-2, 91-100 (2008) · Zbl 1145.15303 · doi:10.1016/j.mcm.2007.08.009
[20] Sun, J.: Matrix perturbation Analysis[M] science press (2001)
[21] Absil, P.A., Mahony, R., Sepulchre, R.: Optimization algorithms on matrix Manifolds[M]. Princeton University Press (2009) · Zbl 1147.65043
[22] Edelman, A.; Arias, TA; Smith, ST, The geometry of algorithms with orthogonality constraints[J], SIAM J. Matrix Anal. Appl., 20, 2, 303-353 (1998) · Zbl 0928.65050 · doi:10.1137/S0895479895290954
[23] Absil, P.A., Mahony, R., Trumpf, J.: An extrinsic look at the Riemannian Hessian[C]. In: International Conference on Geometric Science of Information, pp. 361-368. Springer (2013) · Zbl 1323.53014
[24] Zhu, X., A Riemannian conjugate gradient method for optimization on the Stiefel manifold[J], Comput. Optim. Appl., 67, 1, 73-110 (2017) · Zbl 1401.90230 · doi:10.1007/s10589-016-9883-4
[25] Saad, Y.: Iterative Methods for Sparse Linear Systems[M], vol. 82. SIAM (2003) · Zbl 1031.65046
[26] Barzilai, J.; Borwein, JM, Two-point step size gradient methods[J], IMA J. Numer. Anal., 8, 1, 141-148 (1988) · Zbl 0638.65055 · doi:10.1093/imanum/8.1.141
[27] Boumal, N.; Mishra, B.; Absil, PA; Sepulchre, R., Manopt, a Matlab toolbox for optimization on manifolds[J], J. Mach. Learn. Res., 15, 1, 1455-1459 (2014) · Zbl 1319.90003
[28] Yao, TT; Bai, ZJ; Zhao, Z.; Ching, WK, A Riemannian Fletcher-Reeves conjugate gradient method for doubly stochastic inverse eigenvalue problems[J], SIAM J. Matrix Anal. Appl., 37, 1, 215-234 (2016) · Zbl 1376.65061 · doi:10.1137/15M1023051
[29] Zhao, Z.; Jin, XQ; Bai, ZJ, A geometric nonlinear conjugate gradient method for stochastic inverse eigenvalue problems[J], SIAM J. Numer. Anal., 54, 4, 2015-2035 (2016) · Zbl 1342.65119 · doi:10.1137/140992576
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.