On critical points of quadratic low-rank matrix optimization problems

By André Uschmajew, Bart Vandereycken. 2020

20 citations recorded by the source corpus.

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 (RIPs). 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 nonoptimal 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.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Mathematical Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Mathematical Physics

Citations in the corpus

Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, background): “Other gradient descent approaches on manifolds include [100–106].”
Geometric Methods on Low-Rank Matrix and Tensor Manifolds (2020, background): “, [90]), but landscape properties can be directly applied to Riemannian algorithms as well; see [18, 110].”