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 (revised version: March 2020)
Pages: 26
published in: IMA journal of numerical analysis (2020), pp not yet known
DOI number (of the published article): 10.1093/imanum/drz061
Bibtex
Download full preprint: PDF (620 kB)

Abstract:
The absence of spurious local minima in certain nonconvex 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 the Riemannian manifold of low-rank matrices, with a positive semidefinite Riemannian 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 the single global minimum.