Preprint 58/2018

On critical points of quadratic low-rank matrix optimization problems

André Uschmajew and Bart Vandereycken

Contact the author: Please use for correspondence this email.
Submission date: 18. Jul. 2018
Pages: 25
Bibtex
Download full preprint: PDF (592 kB)

Abstract:
The absence of spurious local minima in certain non-convex low-rank matrix recovery problems has been of recent interest in computer science, machine learning, and compressed sensing since it explains the convergence of some low-rank optimization methods to global optima. One such example is low-rank matrix sensing under restricted isometry properties (RIP). It can be formulated as a minimization problem for a quadratic function on a low-rank matrix manifold, with a positive semidefinite Hessian that acts almost like an identity on low-rank matrices. In this work, new estimates for singular values of local minima for such problems are given which lead to improved bounds on RIP constants to ensure absence of non-optimal local minima and sufficiently negative curvature at all other critical points. A geometric viewpoint is taken which is inspired by the fact that the Euclidean distance function to a rank k matrix possesses no critical points on the corresponding embedded submanifold of rank k matrices except for a single global minimum.

03.08.2018, 00:13