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 methods 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.
Similar content being viewed by others
References
Abraham, R., Marsden, J.E.: Foundations of Mechanics. Benjamin/Cummings Publishing, Reading (1978)
Absil, P.-A., Mahony, R., Sepulchre, R.: Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton (2008)
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)
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)
Arnold, V.I.: Mathematical Methods of Classical Mechanics, 2nd edn. Springer, Newyork (1989)
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)
Ferrer, J., García, M.I., Puerta, F.: Differentiable families of subspaces. Linear Algebra Appl. 199, 229–252 (1994)
Fujii, K.: Note on coherent states and adiabatic connections, curvatures. J. Math. Phys. 41, 4406–4412 (2000)
Gajic, Z., Qureshi, M.T.J.: Lyapunov Matrix Equation in System Stability and Control. Academic Press, Inc, New York (1995)
Golub, G.H., Loan, C.F.V.: Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences, 3rd edn. Johns Hopkins University Press, Baltimore (1996)
Helmke, U., Moore, J.B.: Optimization and Dynamical Systems. Communications and Control Engineering Series. Springer, London (1994) (With a foreword by R. Brockett)
Helmke, U., Huper, K., Trumpf, J.: Newton’s method on Grassmann manifolds. arXiv:0709.2205v2 (2007)
Nocedal, J., Wright, S.J.: Numerical Optimization. Springer Series in Operations Research. Springer, New York (1999)
Sato, H., Iwai, T.: A Riemannian optimization approach to the matrix singular value decomposition. SIAM. J. Optim. 23(1), 188–212 (2013)
Snyman, J.A.: Practical Mathematical Optimization: An Introduction to Basic Optimization Theory and Classical and New Gradient-Based Algorithms. Springer, New York (2005)
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)
Trefethen, L.N., Bau, D.: Numerical Linear Algebra. SIAM (1997)
Wong, Y.-C.: Differential geometry of Grassmann manifolds. Proc. Natl. Acad. Sci. USA 57, 589–594 (1967)
Author information
Authors and Affiliations
Corresponding author
Appendix A: Proof of Proposition 2.4
Appendix A: Proof of Proposition 2.4
In this section, we give the proof of Proposition 2.4 on the variational principle.
Proof
Since the geodesic equation of a Riemannian manifold is viewed as the equation of motion of a free particle on the Riemannian manifold [5], we consider the Lagrangian \(L\) of a free particle on the Grassmann manifold (2.13), which is put in the form
where \(\Omega \) and \(\lambda \) are Lagrange multipliers, and where \(\Omega \) should be a symmetric matrix on account of the fact that \(X^2-X\) is symmetric. The variation of the Lagrangian \(L\) is given by and calculated as
On the variational principle, we have
for any \(\delta X\) subject to the condition \(\delta X(t_1)=\delta X(t_2)=0\). From (6.2) and (6.3), we obtain
Our next task is to determine \(\Omega \) and \(\lambda \). Transposing Eq. (6.4), we have
Equations (6.4) and (6.7) are put together to provide
Multiplying (6.4) by \(X\) from the right and using \(X^2=X\), we obtain
We see that \({\ddot{X}}X=X{\ddot{X}}\) from (6.8) and (6.9). Putting together (6.9) and (6.4), we have
On the other hand, differentiating \(X^2=X\) with respect to \(t\), we obtain
Since \({\ddot{X}}X=X{\ddot{X}}\), the above equation becomes
On account of (6.12), Eq. (6.10) is put in the form
Substituting (6.13) for \(\Omega \) in (6.4), we obtain
Since \({\dot{X}} X+X{\dot{X}}={\dot{X}}\), one has \({\dot{X}}^2X+{\dot{X}}X{\dot{X}}={\dot{X}}^2\), and hence Eq. (6.14) is brought into
This completes the proof. \(\square \)
About this article
Cite this article
Sato, H., Iwai, T. Optimization algorithms on the Grassmann manifold with application to matrix eigenvalue problems. Japan J. Indust. Appl. Math. 31, 355–400 (2014). https://doi.org/10.1007/s13160-014-0141-9
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s13160-014-0141-9
Keywords
- Grassmann manifold
- Riemannian optimization
- Steepest descent method
- Newton’s method
- Rayleigh quotient
- Lyapunov equation