Provable Memory-efficient Online Robust Matrix Completion

Abstract

Robust Matrix Completion (RMC) is the problem of estimating a low-rank matrix in the presence of missing entries and element-wise (sparse) outliers. In this work, we study the RMC problem with the extra assumption that the clean data is generated from either a fixed or a slowly-changing low-dimensional subspace and introduce a provably correct online algorithm for solving it. Our problem can also be interpreted as that of Robust Subspace Tracking with missing data (RST-miss); with "robust" referring to robustness to sparse outliers. Our proposed method, called NORST-miss-robust, and its guarantee both rely on the Recursive Projected Compressive Sensing (ReProCS) framework introduced in our earlier work. We also argue that NORST-miss-robust enjoys near-optimal memory complexity, tracks subspace changes with near-optimal delay, and has time complexity that is order-wise equal to that of vanilla PCA. Detailed experimental comparisons showing the practical advantages of our method are also shown.