×

Optimization algorithms on the Grassmann manifold with application to matrix eigenvalue problems. (English) Zbl 1306.65189

Authors’ abstract: “This article deals with the Grassmann manifold as a submanifold of the matrix Euclidean space, that is, as the set of all orthogonal projection matrices of constant rank, and sets up several optimization algorithms in terms of such matrices. Interest will center on the steepest descent and Newton’s method together with applications to matrix eigenvalue problems. It is shown that Newton’s equation in the proposed Newton’s method applied to the Rayleigh quotient minimization problem takes the form of a Lyapunov equation, for which an existing efficient algorithm can be applied, and thereby the present Newton’s method works efficiently. It is also shown that in case of degenerate eigenvalues the optimal solutions form a submanifold diffeomorphic to a Grassmann manifold of lower dimension. Furthermore, to generate globally converging sequences, this article provides a hybrid method composed of the steepest descent and Newton’s methods on the Grassmann manifold together with convergence analysis.” Numerical experiments are given to show the convergence behaviour of the hybrid method.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65K05 Numerical mathematical programming methods
49M15 Newton-type methods

References:

[1] Abraham, R., Marsden, J.E.: Foundations of Mechanics. Benjamin/Cummings Publishing, Reading (1978) · Zbl 0393.70001
[2] Absil, P.-A., Mahony, R., Sepulchre, R.: Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton (2008) · Zbl 1147.65043
[3] Absil, P.-A., Mahony, R., Sepulchre, R.: Riemannian geometry of Grassmann manifolds with a view on algorithmic computation. Acta Appl. Math. 80(2), 199–220 (2004) · Zbl 1052.65048
[4] Adler, R.L., Dedieu, J.P., Margulies, J.Y., Martens, M., Shub, M.: Newton’s method on Riemannian manifolds and a geometric model for the human spine. IMA J. Numer. Anal. 22(3), 359–390 (2002) · Zbl 1056.92002
[5] Arnold, V.I.: Mathematical Methods of Classical Mechanics, 2nd edn. Springer, Newyork (1989)
[6] Edelman, A., Arias, T.A., Smith, S.T.: The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Anal. Appl. 20(2), 303–353 (1998) · Zbl 0928.65050
[7] Ferrer, J., García, M.I., Puerta, F.: Differentiable families of subspaces. Linear Algebra Appl. 199, 229–252 (1994) · Zbl 0803.58010
[8] Fujii, K.: Note on coherent states and adiabatic connections, curvatures. J. Math. Phys. 41, 4406–4412 (2000) · Zbl 1032.81519
[9] Gajic, Z., Qureshi, M.T.J.: Lyapunov Matrix Equation in System Stability and Control. Academic Press, Inc, New York (1995) · Zbl 1153.93300
[10] Golub, G.H., Loan, C.F.V.: Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences, 3rd edn. Johns Hopkins University Press, Baltimore (1996)
[11] Helmke, U., Moore, J.B.: Optimization and Dynamical Systems. Communications and Control Engineering Series. Springer, London (1994) (With a foreword by R. Brockett) · Zbl 0943.93001
[12] Helmke, U., Huper, K., Trumpf, J.: Newton’s method on Grassmann manifolds. arXiv:0709.2205v2 (2007)
[13] Nocedal, J., Wright, S.J.: Numerical Optimization. Springer Series in Operations Research. Springer, New York (1999) · Zbl 0930.65067
[14] Sato, H., Iwai, T.: A Riemannian optimization approach to the matrix singular value decomposition. SIAM. J. Optim. 23(1), 188–212 (2013) · Zbl 1267.65070
[15] Snyman, J.A.: Practical Mathematical Optimization: An Introduction to Basic Optimization Theory and Classical and New Gradient-Based Algorithms. Springer, New York (2005) · Zbl 1104.90003
[16] Tanimura, S., Nakahara, M., Hayashi, D.: Exact solutions of the isoholonomic problem and the optimal control problem in holonomic quantum computation. J. Math. Phys. 46, 022101 (2005) · Zbl 1076.81009
[17] Trefethen, L.N., Bau, D.: Numerical Linear Algebra. SIAM (1997) · Zbl 0874.65013
[18] Wong, Y.-C.: Differential geometry of Grassmann manifolds. Proc. Natl. Acad. Sci. USA 57, 589–594 (1967) · Zbl 0154.21404
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.