AltMinSense and AltMinComplete (Alternating Minimization for Low-Rank Matrix Sensing and Completion)

The first globally provable alternating least-squares algorithms — *AltMinSense* for rank-$k$ matrix sensing $\mathcal{A}(M) = b$ and *AltMinComplete* for rank-$k$ matrix completion $P_\Omega(M)$ — introduced by Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi (2013). Parameterizing the rank-$k$ estimate in factored form $X = U V^\top$ ($U\in\mathbb{R}^{m\times k}, V\in\mathbb{R}^{n\times k}$), the algorithms initialize $U^0$ from the top-$k$ left singular vectors of the back-projected measurements ($\sum_{i=1}^d A_i b_i$ for sensing; rescaled $P_\Omega(M)/p$ followed by entrywise magnitude clipping at $2\mu\sqrt{k/m}$ for completion) and alternate between exact convex least-squares updates $\widehat{V}^{t+1} = \arg\min_V \|\mathcal{A}(U^t V^\top) - b\|_2^2$ (or $\|P_{\Omega_{2t+1}}(U^t V^\top - M)\|_F^2$) and QR orthonormalization $V^{t+1} = \mathrm{QR}(\widehat{V}^{t+1})$, followed symmetrically by $\widehat{U}^{t+1}$ and $U^{t+1} = \mathrm{QR}(\widehat{U}^{t+1})$. By expressing each least-squares step as a perturbed power iteration $\widehat{V}^{t+1} = V^*\Sigma^*(U^*)^\top U^t - F$ where $F = B^{-1}((U^t)^\top U^* B - C)V^*\Sigma^*$ (Equation 4), Theorems 2.2 and 2.5 prove geometric decay $\mathrm{dist}(U^t,U^*) \le (1/2)^t$ and $\|M - \widehat{U}^T(V^T)^\top\|_F \le \epsilon$ in $T = O(\log(\|M\|_F/\epsilon))$ iterations.