Optimization on manifolds : methods and applications

[en] Summary. This paper provides an introduction to the topic of optimization on manifolds. The approach taken uses the language of differential geometry, however, we choose to emphasise the intuition of the concepts and the structures that are important in generating practical numerical algorithms rather than the technical details of the formulation. There are a number of algorithms that can be applied to solve such problems and we discuss the steepest descent and Newton’s method in some detail as well as referencing the more important of the other approaches. There are a wide range of potential applications that we are aware of, and we briefly discuss these applications, as well as explaining one or two in more detail.

Disciplines :

Electrical & electronics engineering

Author, co-author :

Absil, P.-A.; Université Catholique de Louvain - UCL > Department of Mathematical Engineering

Mahony, R.; Australian National University

Sepulchre, Rodolphe ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation

Language :

English

Title :

Optimization on manifolds : methods and applications

Publication date :

2010

Main work title :

Recent Advances in Optimization and its Applications in Engineering

Publisher :

Springer-Verlag

Pages :

125-144

Available on ORBi :

since 07 November 2010

Statistics

Number of views

151 (3 by ULiège)

Number of downloads

1627 (1 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

P.-A. Absil. Numerical representations of a universal subspace flow for linear programs. Communications in Information and Systems, 8(2):71-84, 2009.
P.-A. Absil, C. G. Baker, and K. A. Gallivan. Trust-region methods on Riemannian manifolds. Found. Comput. Math., 7(3):303-330, July 2007.
P.-A. Absil and K. A. Gallivan. Joint diagonalization on the oblique manifold for independent component analysis. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), volume 5, pages V-945-V-948, 2006.
P.-A. Absil, R. Mahony, and R. Sepulchre. Riemannian geometry of Grassmann manifolds with a view on algorithmic computation. Acta Appl. Math., 80(2):199-220, January 2004.
P.-A. Absil, R. Mahony, and R. Sepulchre. Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton, NJ, 2008.
P.-A. Absil, Jochen Trumpf, Robert Mahony, and Ben Andrews. All roads lead to Newton: Feasible second-order methods for equality-constrained optimization. Technical Report UCL-INMA-2009.024, UCLouvain, 2009.
Roy L. Adler, Jean-Pierre Dedieu, Joseph Y. Margulies, Marco Martens, and Mike Shub. Newton's method on Riemannian manifolds and a geometric model for the human spine. IMA J. Numer. Anal., 22(3):359-390, July 2002.
Bijan Afsari and P. S. Krishnaprasad. Some gradient based joint diagonalization methods for ICA. In Springer LCNS Series, editor, Proceedings of the 5th International Conference on Independent Component Analysis and Blind Source Separation, 2004.
Gregory Ammar and Clyde Martin. The geometry of matrix eigenvalue methods. Acta Appl. Math., 5(3):239-278, 1986.
C. G. Baker, P.-A. Absil, and K. A. Gallivan. An implicit trust-region method on Riemannian manifolds. IMA J. Numer. Anal., 28(4):665-689, 2008.
Christopher G. Baker. Riemannian manifold trust-region methods with applications to eigenproblems. PhD thesis, School of Computational Science, Florida State University, Summer Semester 2008.
M. Baumann and U. Helmke. Riemannian subspace tracking algorithms on Grassmann manifolds. In Proceedings of the 46th IEEE Conference on Decision and Control, 2007.
Silvère Bonnabel and Rodolphe Sepulchre. Riemannian metric and geometric mean for positive semidefinite matrices of fixed rank. SIAM J. Matrix Anal. Appl., 31(3):1055-1070, 2009.
Thomas J. Bridges and Sebastian Reich. Computing Lyapunov exponents on a Stiefel manifold. Phys. D, 156(3-4):219-238, 2001.
Hasan Ertan Çetingül and René Vidal. Intrinsic mean shift for clustering on Stiefel and Grassmann manifolds. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR'09), 2009.
Aris Daniilidis, Warren Hare, and Jérôme Malick. Geometrical interpretation of the predictor-corrector type algorithms in structured optimization problems. Optimization, 55(5-6):481-503, 2006.
Jean-Pierre Dedieu, Gregorio Malajovich, and Mike Shub. On the curvature of the central path of linear programming theory. Found. Comput. Math., 5(2):145-171, 2005.
Alan Edelman, Tomás A. Arias, and Steven T. Smith. The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Anal. Appl., 20(2):303- 353, 1998.
L. Eldén and B. Savas. A Newton-Grassmann method for computing the best multi-linear rank-(r1; r2; r3) approximation of a tensor. SIAM J. Matrix Anal. Appl., 31:248-271, 2009.
Lars Eldén and Haesun Park. A Procrustes problem on the Stiefel manifold. Numer. Math., 82(4):599-619, 1999.
Hermann Grassmann. Wôrterbuch zum Rig-Veda, 1873. Leipzig.
Uwe Helmke, Knut Hüper, Pei Yean Lee, and John B. Moore. Essential matrix estimation using Gauss-Newton iterations on a manifold. Int. J. Computer Vision, 74(2):117-136, 2007.
Uwe Helmke, Knut Hüper, and Jochen Trumpf. Newton's method on Grassmann manifolds, September 2007. arXiv:0709.2205v2.
Uwe Helmke and John B. Moore. Optimization and Dynamical Systems. Communications and Control Engineering Series. Springer-Verlag London Ltd., London, 1994. With a foreword by R. Brockett.
Magnus R. Hestenes and Eduard Stiefel. Methods of conjugate gradients for solving linear systems. J. Research Nat. Bur. Standards, 49:409-436 (1953), 1952.
Knut Hüper, Hao Shen, and Abd-Krim Seghouane. Local convergence properties of FastICA and some generalisations. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), volume 5, pages V-1009-V-1012, 2006.
M. Ishteva, L. De Lathauwer, P.-A. Absil, and S. Van Huffel. Best low multilinear rank approximation of higher-order tensors, based on the Riemannian trust-region scheme. Technical Report 09-142, ESAT-SISTA, K.U.Leuven, Belgium, 2009.
Jens Jordan and Uwe Helmke. Controllability of the QR-algorithm on Hessenberg flags. In David S. Gilliam and Joachim Rosenthal, editors, Proceeding of the Fifteenth International Symposium on Mathematical Theory of Network and Systems (MTNS 2002), 2002.
Shantanu H. Joshi, Eric Klassen, Anuj Srivastava, and Ian Jermyn. A novel representation for Riemannian analysis of elastic curves in Rn. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2007.
M. Journée, F. Bach, P.-A. Absil, and R. Sepulchre. Low-rank optimization for semidefinite convex problems, 2008. arXiv:0807.4423.
E. Klassen, A. Srivastava, M. Mio, and S.H. Joshi. Analysis of planar shapes using geodesic paths on shape spaces. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(3):372-383, 2004.
Eric Klassen and Anuj Srivastava. Geodesics between 3D closed curves using path-straightening. In A. Leonardis, H. Bischof, and A. Pinz, editors, ECCV 2006, Part I" volume 3951 of LNCS, pages 95-106. Springer-Verlag, Berlin Heidelberg, 2006.
John M. Lee. Introduction to smooth manifolds, volume 218 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2003.
Pei Yean Lee and John B. Moore. Pose estimation via a Gauss-Newton-onmanifold approach. In Proceedings of the 16th International Symposium on Mathematical Theory of Network and System (MTNS), Leuven, 2004.
Claude Lemaréchal, François Oustry, and Claudia Sagastizábal. The ULagrangian of a convex function. Trans. Amer. Math. Soc., 352(2):711-729, 2000.
A. S. Lewis. Active sets, nonsmoothness, and sensitivity. SIAM J. Optim., 13(3):702-725 (electronic) (2003), 2002.
Chong Li, Genaro López, and Victoria Martín-Márquez. Monotone vector fields and the proximal point algorithm on Hadamard manifolds. J. London Math. Soc., 79(3):663-683, 2009.
R. Lippert and A. Edelman. Nonlinear eigenvalue problems with orthogonality constraints (Section 9.4). In Zhaojun Bai, James Demmel, Jack Dongarra, Axel Ruhe, and Henk van der Vorst, editors, Templates for the Solution of Algebraic Eigenvalue Problems, pages 290-314. SIAM, Philadelphia, 2000.
Xiuwen Liu, Anuj Srivastava, and Kyle Gallivan. Optimal linear representations of images for object recognition. IEEE Pattern Anal. and Mach. Intell., 26(5):662-666, May 2004.
Eva Lundstrôm and Lars Eldén. Adaptive eigenvalue computations using Newton's method on the Grassmann manifold. SIAM J. Matrix Anal. Appl., 23(3):819-839, 2001/02.
Yi Ma, Jana Kosecka, and Shankar S. Sastry. Optimization criteria and geometric algorithms for motion and structure estimation. Int. J. Computer Vision, 44(3):219-249, 2001.
Jonathan H. Manton. A centroid (Karcher mean) approach to the joint approximate diagonalization problem: The real symmetric case. Digital Signal Processing, 16(5):468-478, 2005.
Robert Mifflin and Claudia Sagastizábal. On VU-theory for functions with primal-dual gradient structure. SIAM J. Optim., 11(2):547-571 (electronic), 2000.
Scott A. Miller and Jérôme Malick. Newton methods for nonsmooth convex minimization: connections among U-Lagrangian, Riemannian Newton and SQP methods. Math. Program., 104(2-3, Ser. B):609-633, 2005.
Y. Nesterov and A. Nemirovski. Primal central paths and Riemannian distances for convex sets. Found. Comput. Math., 8(5):533-560, 2008.
Yasunori Nishimori and Shotaro Akaho. Learning algorithms utilizing quasigeodesic flows on the Stiefel manifold. Neurocomputing, 67:106-135, 2005.
Yasunori Nishimori, Shotaro Akaho, and Mark D. Plumbley. Natural conjugate gradient on complex flag manifolds for complex independent subspace analysis. In Vera Kurkova-Pohlova, Roman Neruda, and Jan Koutnik, editors, Artificial Neural Networks - ICANN 2008, volume 5163 of LNCS, pages 165-174. Springer, Berlin Heidelberg, 2008.
Chunhong Qi, Kyle A. Gallivan, and P.-A. Absil. Riemannian BFGS algorithm with applications. In Recent Advances in Optimization and its Applications in Engineering. Springer, 2010. To appear.
Quentin Rentmeesters, P.-A. Absil, and Paul Van Dooren. Identification method for time-varying ARX models. Submitted, 2009.
Chafik Samir, P.-A. Absil, Anuj Srivastava, and Eric Klassen. A gradientdescent method for curve fitting on Riemannian manifolds. Technical Report UCL-INMA-2009.023, UCLouvain, 2009.
Oliver Sander. Geodesic finite elements for Cosserat rods. submitted, 2009.
Berkant Savas and Lek-Heng Lim. Best multilinear rank approximation of tensors with quasi-Newton methods on Grassmannians. Technical Report LITH-MAT-R-2008-01-SE, Department of Mathematics, Linkôpings Universitet, 2008.
Anuj Srivastava and Eric Klassen. Bayesian and geometric subspace tracking. Adv. in Appl. Probab., 36(1):43-56, 2004.
Anuj Srivastava and Xiuwen Liu. Tools for application-driven linear dimension reduction. Neurocomputing, 67:136-160, 2005.
E. Stiefel. Richtungsfelder und Fernparallelismus in n-dimensionalen Mannigfaltigkeiten. Comment. Math. Helv., 8(1):305-353, 1935.
Fabian J. Theis, Thomas P. Cason, and P.-A. Absil. Soft dimension reduction for ICA by joint diagonalization on the Stiefel manifold. In Proc. ICA 2009, volume 5441 of LNCS, pages 354-361, Paraty, Brazil, 2009. Springer.
Frank Tompkins and Patrick J.Wolfe. Bayesian filtering on the Stiefel manifold. In 2nd IEEE International Workshop on Computational Advances in Multi- Sensor Adaptive Processing (CAMPSAP 2007), 2007.
Nickolay T. Trendafilov and Ross A. Lippert. The multimode Procrustes problem. Linear Algebra Appl., 349:245-264, 2002.
Pavan Turaga, Ashok Veeraraghavan, and Rama Chellappa. Statistical analysis on Stiefel and Grassmann manifolds with applications in computer vision. In IEEE Conference on Computer Vision and Pattern Recognition, 2008.
Bart Vandereycken, P.-A. Absil, and Stefan Vandewalle. Embedded geometry of the set of symmetric positive semidefinite matrices of fixed rank. In Proceedings of the IEEE 15th Workshop on Statistical Signal Processing, pages 389-392, 2009.
Bart Vandereycken and Stefan Vandewalle. A Riemannian optimization approach for computing low-rank solutions of Lyapunov equations. Submitted, 2009.
Frank W. Warner. Foundations of differentiable manifolds and Lie groups, volume 94 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1983. Corrected reprint of the 1971 edition.
Gongyun Zhao. Representing the space of linear programs as the Grassmann manifold. Math. Program., 121(2, Ser. A):353-386, 2010.