Solving Weighted Orthogonal Procrustes Problems via a Projected Gradient Method
DOI:
https://doi.org/10.5540/tcam.2024.025.e01786Keywords:
Continuous optimization, constrained optimization, Stiefel manifold, procrustes analysis, projected gradient method.Abstract
This paper proposes a family of line--search methods to deal with weighted orthogonal procrustes problems. In particular, the proposed family uses a search direction based on a convex combination between the Euclidean gradient and the Riemannian gradient of the cost function. The non--monotone line--search of Zhang and Hager, and an adaptive Barzilai--Borwein step--size are the chosen tools, in order to speed up the convergence of the new family of methods. One of the extremes of that convex combination is reduced to well--known spectral projected gradient method, while the another one can be interpreted as a Riemannian steepest descent method. To preserve feasibility of all the iterates, we use a projection operator based on the singular value decomposition, which can be computed efficiently via the spectral decomposition of an appropriate matrix. In addition, we prove that the entire uncountable collection of search directions satisfies a descent condition. Some numerical experiments are provided in order to demonstrate the effectiveness of the new approach.References
Absil, P-A., Robert Mahony, and Rodolphe Sepulchre. Optimization algorithms on matrix manifolds. Princeton University Press, 2008.
Oviedo, Harry. A cyclic delayed weighted steplength for the gradient method. Ricerche di Matematica (2021): 1-13.
Francisco, J. B., and Tiara Martini. Spectral projected gradient method for the procrustes %problem. TEMA (São Carlos) 15 (2014): 83-96.
Birgin, Ernesto G., José Mario Martínez, and Marcos Raydan. Nonmonotone spectral projected gradient methods on convex sets. SIAM Journal on Optimization 10.4 (2000): 1196-1211.
Birgin, Ernesto G., Jose Mario Martínez, and Marcos Raydan. Spectral projected gradient methods: review and perspectives. Journal of Statistical Software 60 (2014): 1-21.
Francisco, J. B., FS Viloche Bazán, and M. Weber Mendonça. Non-monotone algorithm for minimization on arbitrary domains with applications to large-scale orthogonal procrustes problem. Applied Numerical Mathematics 112 (2017): 51-64.
Oviedo, Harry. Proximal Point Algorithm with Euclidean Distance on the Stiefel Manifold. Mathematics 11.11 (2023): 2414.
Oviedo, Harry. Global convergence of Riemannian line search methods with a Zhang-Hager-type condition. Numerical Algorithms 91.3 (2022): 1183-1203.
Oviedo, Harry, Oscar Dalmau, and Rafael Herrera. Two novel gradient methods with optimal step sizes. Journal of Computational Mathematics 39.3 (2021): 375.
Zhang, Zhenyue, Yuyang Qiu, and Keqin Du. Conditions for optimal solutions of unbalanced Procrustes problem on Stiefel manifold. Journal of Computational Mathematics (2007): 661-671.
Jiang, Bo, and Yu-Hong Dai. A framework of constraint preserving update schemes for optimization on Stiefel manifold. Mathematical Programming 153.2 (2015): 535-575.
Luenberger, David G., and Yinyu Ye. Linear and nonlinear programming. Vol. 2. Reading, MA: Addison-wesley, 1984.
Wen, Zaiwen, and Wotao Yin. A feasible method for optimization with orthogonality constraints. Mathematical Programming 142.1-2 (2013): 397-434.
Oviedo, Harry, Oscar Dalmau, and Hugo Lara. Two adaptive scaled gradient projection methods for Stiefel manifold constrained optimization. Numerical Algorithms 87 (2021): 1107-1127.
Edelman, Alan, Tomás A. Arias, and Steven T. Smith. The geometry of algorithms with orthogonality constraints. SIAM journal on Matrix Analysis and Applications 20.2 (1998): 303-353.
Manton, Jonathan H. Optimization algorithms exploiting unitary constraints. IEEE transactions on signal processing 50.3 (2002): 635-650.
Oviedo, Harry, Hugo Lara, and Oscar Dalmau. A non-monotone linear search algorithm with mixed direction on Stiefel manifold. Optimization Methods and Software 34.2 (2019): 437-457.
Zhu, Xiaojing. A Riemannian conjugate gradient method for optimization on the Stiefel manifold. Computational optimization and Applications 67 (2017): 73-110.
Zhang, Hongchao, and William W. Hager. A nonmonotone line search technique and its application to unconstrained optimization. SIAM journal on Optimization 14.4 (2004): 1043-1056.
Barzilai, Jonathan, and Jonathan M. Borwein. Two-point step size gradient methods. IMA journal of numerical analysis 8.1 (1988): 141-148.
Schönemann, Peter H. A generalized solution of the orthogonal procrustes problem. Psychometrika 31.1 (1966): 1-10.
Wen, Zaiwen, et al. Trace-penalty minimization for large-scale eigenspace computation. Journal of Scientific Computing 66 (2016): 1175-1203.
Kokiopoulou, Effrosini, Jie Chen, and Yousef Saad. Trace optimization and eigenproblems in dimension reduction methods. Numerical Linear Algebra with Applications 18.3 (2011): 565-602.
Viklands, Thomas. Algorithms for the weighted orthogonal procrustes problem and other least squares problems. Diss. Datavetenskap, 2006.
Feng, Xu, Wenjian Yu, and Yaohang Li. Faster matrix completion using randomized SVD. 2018 IEEE 30th International conference on tools with artificial intelligence (ICTAI). IEEE, 2018.
Söderkvist, Inge, and Per-Åke Wedin. On condition numbers and algorithms for determining a rigid body movement. BIT Numerical Mathematics 34 (1994): 424-436.
Hurley, John R., and Raymond B. Cattell. The Procrustes program: Producing direct rotation to test a hypothesized factor structure. Behavioral science 7.2 (1962): 258.
Bell, Thomas. Global positioning system-based attitude determination and the orthogonal procrustes problem. Journal of guidance, control, and dynamics 26.5 (2003): 820-822.
Oviedo, Harry. Implicit steepest descent algorithm for optimization with orthogonality constraints. Optimization Letters 16.6 (2022): 1773-1797.
Zhang, Zhenyue, Yuyang Qiu, and Keqin Du. Conditions for optimal solutions of unbalanced Procrustes problem on Stiefel manifold. Journal of Computational Mathematics (2007): 661-671.
Zhang L. H., Yang W. H., Shen C. and Ying J. An eigenvalue-based method for the unbalanced Procrustes problem. SIAM Journal on Matrix Analysis and Applications, 41(3): 957-983, (2020).
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Trends in Computational and Applied Mathematics
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.
Copyright
Authors of articles published in the journal Trends in Computational and Applied Mathematics retain the copyright of their work. The journal uses Creative Commons Attribution (CC-BY) in published articles. The authors grant the TCAM journal the right to first publish the article.
Intellectual Property and Terms of Use
The content of the articles is the exclusive responsibility of the authors. The journal uses Creative Commons Attribution (CC-BY) in published articles. This license allows published articles to be reused without permission for any purpose as long as the original work is correctly cited.
The journal encourages Authors to self-archive their accepted manuscripts, publishing them on personal blogs, institutional repositories, and social media, as long as the full citation is included in the journal's website version.
