Abstract

Least squares optimization on a manifold of equivalence relations, i.e., in the presence of symmetries, appears  in many fields. Two fundamental examples are the generalized eigenvalue problem, a least-square problem with orthogonality constraints, and the matrix completion problem, a least-square problem with rank constraints. The large scale nature of these problems requires us to exploit the problem structure as much as possible. The presentation deals with these structures.

Riemannian optimization has gained much popularity in the recent years because of the particular nature of the orthogonality and rank constraints. 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 show a basic connection between sequential quadratic programming and Riemannian gradient optimization and address the general question of selecting a metric in Riemannian optimization in a way that not only exploits the constraints but also the cost function, that is, exploits the least squares problem structure. 

The proposed method of selecting a Riemannian metric is shown to be particularly insightful and efficient in quadratic optimization with orthogonality and rank constraints, which covers most current applications of Riemannian optimization in matrix manifolds. 

Keywords: Riemannian optimization Sequential quadratic programming, Metric, Preconditioning, Orthogonality, Low-rank