General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds

MaRDI QIDQ6365790zbMATH OpenFDO

Authors Haixiang Zhang, Yingjie Bi, Javad Lavaei

Publication date 21 April 2021

Abstract: This paper considers the global geometry of general low-rank minimization problems via the Burer-Monterio factorization approach. For the rank-$1$ case, we prove that there is no spurious second-order critical point for both symmetric and asymmetric problems if the rank-$2$ RIP constant $delta$ is less than $1/2$. Combining with a counterexample with $delta=1/2$, we show that the derived bound is the sharpest possible. For the arbitrary rank-$r$ case, the same property is established when the rank-$2r$ RIP constant $delta$ is at most $1/3$. We design a counterexample to show that the non-existence of spurious second-order critical points may not hold if $delta$ is at least $1/2$. In addition, for any problem with $delta$ between $1/3$ and $1/2$, we prove that all second-order critical points have a positive correlation to the ground truth. Finally, the strict saddle property, which can lead to the polynomial-time global convergence of various algorithms, is established for both the symmetric and asymmetric problems when the rank-$2r$ RIP constant $delta$ is less than $1/3$. The results of this paper significantly extend several existing bounds in the literature.

This page was built for publication: General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6365790)