No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis

Understand

In this paper we develop a new framework that captures the common landscape underlying the common non-convex low-rank matrix problems including matrix sensing, matrix completion and robust PCA.

• In particular, we show for all above problems (including asymmetric cases): 1) all local minima are also globally optimal; 2) no high-order saddle points exists.
• These results explain why simple algorithms such as stochastic gradient descent have global converge, and efficiently optimize these non-convex objective functions in practice.
• Our framework connects and simplifies the existing analyses on optimization landscapes for matrix sensing and symmetric matrix completion.