On descent algorithms on low-rank matrix varieties (André Uschmajew - University of Bonn)

24.11.2015 14:15 – 15:00

A way to address matrix optimization problems with low-rank constraints are Riemannian optimization algorithms on the smooth manifold of, say, rank-$k$ matrices. If sufficiently gradient-related, the corresponding line-search methods can be seen as discrete gradient flows (or dynamical systems). Similar iterations arise in the context of geometric integrators for dynamical low-rank approximation which attracted recent attention. If not given in advance, a practical problem can be the choice of a suitable rank $k$. But even if the ``correct'' target rank is chosen, the rigorous convergence analysis is hampered by the fact that the manifold of rank-$k$ matrices itself is not closed.

We show how both problems can be addressed by formally considering gradient iterations on the variety of matrices of rank at most $k$, in which the tangential gradient projections in rank-deficient points involve the tangent cones instead of tangent spaces. These tangent cones turn out to have a simple explicit description. Convergence results for specific step-size rules can then be obtained via \L{}ojasiewicz gradient inequality, allowing rank-deficient limit points. Conversely, with this approach, (locally) optimal points with rank at most $k$ can be embedded as starting guess into a variety of higher rank, e.g., $k+1$. In this way, efficient rank-increasing heuristics can be designed. Popular strategies realize this embedding by adding low-rank approximations of the unconstrained antigradient to the current iterate. This heuristic can now be justified from the explicit form of the tangent cone again.

The talk is based on joint work with Reinhold Schneider (TU Berlin) and Bart Vandereycken (University of Geneva).

Lieu

salle 623, Séminaire d'analyse numérique

entrée libre