Search

MiS Preprint Repository

We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.

MiS Preprint
58/2018

On critical points of quadratic low-rank matrix optimization problems

André Uschmajew and Bart Vandereycken

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.

Received:
Jul 18, 2018
Published:
Jul 23, 2018

Related publications

inJournal
2020 Journal Open Access
André Uschmajew and Bart Vandereycken

On critical points of quadratic low-rank matrix optimization problems

In: IMA journal of numerical analysis, 40 (2020) 4, pp. 2626-2651