Near-Optimal Robust Matrix Completion via Non-convex Optimization

  • Prateek Jain | Microsoft

Several important applications require completion a low-rank matrix in presence of gross outliers. Examples include robust PCA with missing entries, robust recommendation system, foreground background separation in sublinear time etc. Existing solutions for this problem do not scale for large data and do not have optimal sample complexity/outlier complexity bounds. In this talk, we will present a simple non-convex optimization based method that is scalable, easy to implement and needs few parameters. Moreover, despite using a non-convex optimization approach, we show that our method achieves linear rate of convergence and solves the problem in nearly optimal time, using nearly optimal number of samples and outliers, thus significantly improving upon the existing state-of-the-art results. Moreover, our experiments show that the method is an order of magnitude faster than the existing methods and leads to a video foreground extraction technique that significantly outperforms existing standard techniques for the problem.

Series: Microsoft Research Talks