Nonconvex Matrix Completion Optimization Landscape Without Spurious Local Minima

A global nonconvex optimization landscape characterization (introduced by Rong Ge, Jason D. Lee, and Tengyu Ma in 2016) proving that the Burer–Monteiro factored matrix completion objective $f(\boldsymbol{X}) = \frac{1}{2p}\|\mathcal{P}_\Omega(\boldsymbol{M} - \boldsymbol{X}\boldsymbol{X}^\top)\|_F^2 + \lambda R(\boldsymbol{X})$ over $\boldsymbol{X} \in \mathbb{R}^{d\times r}$ with quartic row-norm incoherence regularizer $R(\boldsymbol{X}) = \sum_{i=1}^d (\|\boldsymbol{X}_i\|_2 - \alpha)_+^4$ (Equation 5.1) has **no spurious local minima** and obeys the global $(\theta,\gamma,\zeta)$-strict saddle property (Definition 2.1). Specifically, when a positive semidefinite rank-$r$ matrix $\boldsymbol{M} = \boldsymbol{Z}\boldsymbol{Z}^\top$ satisfies $\mu$-incoherence ($\|\boldsymbol{Z}_i\|_2 \le \mu\sqrt{r/d}\sigma_1(\boldsymbol{Z})$) and entries are observed independently with probability $p \ge \tilde{\Omega}(\frac{\mu^4 r^6 \kappa^4}{d\varepsilon^2})$, Theorem 1.1 and Theorem 5.3 prove that every critical point $\nabla f(\boldsymbol{X}) = \boldsymbol{0}$ is either (1) a global minimum satisfying $\boldsymbol{X}\boldsymbol{X}^\top = \boldsymbol{M}$ (up to $\varepsilon$ in the noisy case), or (2) a strict saddle point where the Hessian exhibits strictly negative curvature $\lambda_{\min}(\nabla^2 f(\boldsymbol{X})) \le -\Omega(\mu^2 \sigma_r(\boldsymbol{M}) r/d) < 0$. The proof constructs an explicit escape direction $\boldsymbol{\Delta} = \boldsymbol{X} - \boldsymbol{Z}\boldsymbol{R}$ aligned to $\boldsymbol{Z}$ via the Procrustes rotation $\boldsymbol{R}$ and combines concentration of the sampling operator $\|\mathcal{P}_\Omega(\boldsymbol{A}) - p\boldsymbol{A}\|_F^2$ on low-rank incoherent tangent matrices with the directional convexity inequality $\langle \nabla R(\boldsymbol{X}), \boldsymbol{\Delta}\rangle \ge 0$ (Claim C.3, Lemma 5.7) to show that $\langle \boldsymbol{\Delta}, \nabla^2 f(\boldsymbol{X})\boldsymbol{\Delta}\rangle \ge 0$ combined with $\nabla f(\boldsymbol{X}) = \boldsymbol{0}$ forces $\|\boldsymbol{M} - \boldsymbol{X}\boldsymbol{X}^\top\|_F = 0$.