Sketching Dictionary Based Robust PCA in Large Matrices

In this paper, our goal is to rapidly locating a few outliers and recover a low dimensional space spanned by inliers, with the particular interest when the outliers have known basis. A simple two-step approach is proposed based on a sketching procedure with theoretical guarantees for the performance. We show that exact identification of the outliers and recovery of the subspace can be achieved using sketched samples as few as the rank plus the number of outliers, ignoring logarithmic factors. This results in significant improvement on both sampling and computational efficiency. Comprehensive numerical experiments are provided to show the efficiency of our proposed method.