Bart Vandereycken

On critical points of quadratic low-rank matrix optimization problems

by ,

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 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.

Download links:

[pdf] [doi]

Reference:

A. Uschmajew, B. Vandereycken, "On critical points of quadratic low-rank matrix optimization problems", In IMA J. Numer. Anal., 2020.

Bibtex Entry:

@article{Uschmajew_V:2020,
    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 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.},
    Author = {Uschmajew, A. and Vandereycken, B.},
    Journal = {IMA J. Numer. Anal.},
    Title = {On critical points of quadratic low-rank matrix optimization problems},
    Year = {2020},
    Pdf = {http://www.unige.ch/math/vandereycken/papers/published_Uschmajew_V_2020.pdf},
    Doi = {10.1093/imanum/drz061}   
    }