Nearly Optimal Robust Matrix Completion
[edit]
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:797805, 2017.
Abstract
In this paper, we consider the problem of Robust Matrix Completion (RMC) where the goal is to recover a lowrank matrix by observing a small number of its entries out of which a few can be arbitrarily corrupted. We propose a simple projected gradient descentbased method to estimate the lowrank matrix that alternately performs a projected gradient descent step and cleans up a few of the corrupted entries using hardthresholding. Our algorithm solves RMC using nearly optimal number of observations while tolerating a nearly optimal number of corruptions. Our result also implies significant improvement over the existing time complexity bounds for the lowrank matrix completion problem. Finally, an application of our result to the robust PCA problem (lowrank+sparse matrix separation) leads to nearly linear time (in matrix dimensions) algorithm for the same; existing stateoftheart methods require quadratic time. Our empirical results corroborate our theoretical results and show that even for moderate sized problems, our method for robust PCA is an order of magnitude faster than the existing methods.
Related Material


