Convex and Nonconvex Optimization Bridging for Robust PCA under Noise, Outliers, and Missing Data

A unified convex–nonconvex optimization analysis and estimation framework (introduced by Yuxin Chen, Jianqing Fan, Cong Ma, and Yuling Yan in 2021) for noisy Robust Principal Component Analysis with missing data, where partial observations on $\Omega \subseteq [n]\times[n]$ obey $Y_{i,j} = M_{i,j}^\star + S_{i,j}^\star + E_{i,j}$ with rank-$r$ positive semidefinite signal $\boldsymbol{M}^\star = \boldsymbol{U}^\star\boldsymbol{U}^{\star\top}$, sparse arbitrary-magnitude outliers $\boldsymbol{S}^\star$, and dense sub-Gaussian noise $\boldsymbol{E}$. Rather than constructing a fragile least-squares dual certificate directly for the convex Principal Component Pursuit (PCP) program $\min_{\boldsymbol{M}\succeq\boldsymbol{0},\boldsymbol{S}} \frac{1}{2}\|\mathcal{P}_\Omega(\boldsymbol{M}+\boldsymbol{S}-\boldsymbol{Y})\|_F^2 + \lambda\,\mathrm{Tr}(\boldsymbol{M}) + \tau\|\mathcal{P}_\Omega(\boldsymbol{S})\|_1$ (Equation 2.3), the method analyzes an auxiliary nonconvex Burer–Monteiro factored estimator $\min_{\boldsymbol{U}\in\mathbb{R}^{n\times r},\boldsymbol{S}} \frac{1}{2}\|\mathcal{P}_\Omega(\boldsymbol{U}\boldsymbol{U}^\top+\boldsymbol{S}-\boldsymbol{Y})\|_F^2 + \frac{\lambda}{2}\|\boldsymbol{U}\|_F^2 + \tau\|\mathcal{P}_\Omega(\boldsymbol{S})\|_1$ (Equation 3.1) via alternating gradient descent on $\boldsymbol{U}$ and exact soft-thresholding $\boldsymbol{S}^{t+1} = \mathcal{S}_\tau(\mathcal{P}_\Omega(\boldsymbol{Y} - \boldsymbol{U}^t\boldsymbol{U}^{t\top}))$ (Algorithm 1). Using leave-one-out trajectory analysis to prove that the nonconvex stationary point $(\widehat{\boldsymbol{U}},\widehat{\boldsymbol{S}})$ satisfies $\|\widehat{\boldsymbol{U}}\widehat{\boldsymbol{H}} - \boldsymbol{U}^\star\|_{2,\infty} \lesssim \frac{\sigma\sqrt{n\log n}}{p\sqrt{\sigma_{\min}}} \sqrt{\frac{\mu r}{n}}$ and strict residual spectral bound $\|\mathcal{P}_\Omega(\boldsymbol{Y} - \widehat{\boldsymbol{U}}\widehat{\boldsymbol{U}}^\top - \widehat{\boldsymbol{S}})\| < \lambda$ (Lemma 4.1), Proposition 4.1 proves that $(\widehat{\boldsymbol{M}}_{\mathrm{cvx}} = \widehat{\boldsymbol{U}}\widehat{\boldsymbol{U}}^\top, \widehat{\boldsymbol{S}}_{\mathrm{cvx}} = \widehat{\boldsymbol{S}})$ automatically satisfies the KKT optimality conditions of the convex program (Equation 2.3). Consequently, Theorem 2.1 establishes that the convex PCP solution is automatically exact rank-$r$, achieves optimal entrywise $\|\widehat{\boldsymbol{M}}_{\mathrm{cvx}} - \boldsymbol{M}^\star\|_\infty$ and $\|\widehat{\boldsymbol{M}}_{\mathrm{cvx}} - \boldsymbol{M}^\star\|_F$ error bounds without extra $\sqrt{n}$ suboptimal factors, and recovers the outlier support $\mathrm{supp}(\boldsymbol{S}^\star)$.