OptSpace (Degree Trimming, Rank-r Spectral Projection, and Grassmann Manifold Matrix Completion)

A three-stage spectral and Riemannian manifold algorithm (*OptSpace*, introduced by Raghunandan H. Keshavan, Andrea Montanari, and Sewoong Oh in 2010) for reconstructing a rank-$r$ matrix $M = U\Sigma V^\top \in \mathbb{R}^{m\times n}$ from a small uniformly sampled subset of entries $E\subseteq [m]\times [n]$: (1) *Degree Trimming*, which sets to zero all rows in $M^E$ with degree exceeding $2|E|/m$ and all columns with degree exceeding $2|E|/n$ to form $\widetilde{M}^E$, suppressing heavy-tailed vertex-degree singular vectors of order $\sqrt{\log n/\log\log n}$ in the sparse $|E| = \Theta(n)$ regime; (2) *Rank-$r$ Spectral Projection* $\mathrm{T}_r(\widetilde{M}^E) = \frac{mn}{|E|}\sum_{i=1}^r \sigma_i x_i y_i^\top$, which achieves relative RMSE $\le C\kappa^2 \sqrt{r\alpha n/|E|}$ (Theorem 1.1); and (3) *Grassmann Manifold Cleaning*, which minimizes the variable-projected discrepancy $F(X,Y) = \min_{S\in\mathbb{R}^{r\times r}} \frac{1}{2}\|\mathcal{P}_E(M - X S Y^\top)\|_F^2$ over $(X,Y)\in\mathrm{G}(m,r)\times\mathrm{G}(n,r)$ ($X^\top X = m I_r$, $Y^\top Y = n I_r$), where $F(X,Y)$ is locally strongly convex via lower curvature bound $\mathrm{d}^2 F(t)/\mathrm{d}t^2|_{t=0} \ge C\epsilon^2 \sigma_{\min}^4 (d(X,U)^2 + d(Y,V)^2)$ (Lemma 6.5) and converges to exact recovery $X_k S_k Y_k^\top \to M$ once $|E| \ge C\kappa^6 n r \max(\mu_0 \log n, \mu_0^2 r \kappa^4)$ (Theorem 1.2).