Timezone: »
Poster
General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds
Haixiang Zhang · Yingjie Bi · Javad Lavaei
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.
Author Information
Haixiang Zhang (University of California, Berkeley)
Yingjie Bi (University of California, Berkeley)
Javad Lavaei (University of California, Berkeley)
More from the Same Authors
-
2021 Poster: Stochastic $L^\natural$-convex Function Minimization »
Haixiang Zhang · Zeyu Zheng · Javad Lavaei -
2018 Poster: How Much Restricted Isometry is Needed In Nonconvex Matrix Recovery? »
Richard Zhang · Cedric Josz · Somayeh Sojoudi · Javad Lavaei -
2018 Spotlight: How Much Restricted Isometry is Needed In Nonconvex Matrix Recovery? »
Richard Zhang · Cedric Josz · Somayeh Sojoudi · Javad Lavaei -
2018 Poster: A theory on the absence of spurious solutions for nonconvex and nonsmooth optimization »
Cedric Josz · Yi Ouyang · Richard Zhang · Javad Lavaei · Somayeh Sojoudi