Poster
General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds
Haixiang Zhang · Yingjie Bi · Javad Lavaei
Keywords: [ Optimization ]
Abstract:
This paper considers the global geometry of general low-rank minimization problems via the Burer-Monterio factorization approach. For the rank- case, we prove that there is no spurious second-order critical point for both symmetric and asymmetric problems if the rank- RIP constant is less than . Combining with a counterexample with , we show that the derived bound is the sharpest possible. For the arbitrary rank- case, the same property is established when the rank- RIP constant is at most . We design a counterexample to show that the non-existence of spurious second-order critical points may not hold if is at least . In addition, for any problem with between and , 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- RIP constant is less than . The results of this paper significantly extend several existing bounds in the literature.
Chat is not available.