Fast and Provable Nonconvex Robust Matrix Completion
For practitioners needing robust matrix completion from corrupted observations, this method offers faster and provably better guarantees than prior convex and non-convex approaches.
The paper proposes ARMC, a non-convex method for robust matrix completion that accelerates prior work via an explicit subspace projection step, achieving entrywise linear convergence with improved sample complexity and outlier sparsity bounds over convex relaxation, and outperforming existing non-convex methods in experiments.
We study the robust matrix completion (RMC) problem subject to both sparse outliers and stochastic noise. A non-convex method termed Accelerated Robust Matrix Completion (ARMC) is proposed, which accelerates a prior non-convex approach by incorporating an explicit subspace projection step into the low-rank update, leading to significantly improved computational efficiency. Through a delicate analysis based on the leave-one-out technique, the entrywise linear convergence guarantee of ARMC has been established. Notably, the derived bounds for sample complexity and outlier sparsity improve upon existing guarantees of the convex relaxation approach that also accounts for both sparse outliers and stochastic noise. Moreover, numerical experiments on synthetic and real data show that ARMC is superior to existing non-convex RMC methods.