[en] This thesis deals with least-squares optimization on a manifold of equivalence relations, e.g., in the presence of symmetries which arise frequently in many applications. While least-squares cost functions remain a popular way to model large-scale problems, the additional symmetry constraint should be interpreted as a way to make the modeling robust. Two fundamental examples are the matrix completion problem, a least-squares problem with rank constraints and the generalized eigenvalue problem, a least-squares problem with orthogonality constraints. The possible large-scale nature of these problems demands to exploit the problem structure as much as possible in order to design numerically efficient algorithms.
The constrained least-squares problems are tackled in the framework of Riemannian optimization that has gained much popularity in recent years because of the special nature of orthogonality and rank constraints that have particular symmetries. Previous work on Riemannian optimization has mostly focused on the search space, exploiting the differential geometry of the constraint but disregarding the role of the cost function. We, on the other hand, propose to take both cost and constraints into account to propose a tailored Riemannian geometry. This is achieved by proposing novel Riemannian metrics. To this end, we show a basic connection between sequential quadratic programming and Riemannian gradient optimization and address the general question of selecting a metric in Riemannian optimization. We revisit quadratic optimization problems with orthogonality and rank constraints by generalizing various existing methods, like power, inverse and Rayleigh quotient iterations, and proposing novel ones that empirically compete with state-of-the-art algorithms.
Overall, this thesis deals with exploiting two fundamental structures, least-squares and symmetry, in nonlinear optimization.
Disciplines :
Electrical & electronics engineering
Author, co-author :
Mishra, Bamdev ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation
Language :
English
Title :
A Riemannian approach to large-scale constrained least-squares with symmetries
Defense date :
20 October 2014
Institution :
ULiège - Université de Liège
Degree :
Doctorat en Sciences de l’ingénieur
Promotor :
Sepulchre, Rodolphe ; Université de Liège - ULiège > Montefiore Institute of Electrical Engineering and Computer Science
Bach, Francis
President :
Wehenkel, Louis ; Université de Liège - ULiège > Montefiore Institute of Electrical Engineering and Computer Science
Jury member :
De Lathauwer, Lieven
Louveaux, Quentin ; Université de Liège - ULiège > Montefiore Institute of Electrical Engineering and Computer Science
