Abstract

A remarkably simple, yet powerful, algorithm termed Coherence Pursuit for robust Principal Component Analysis (PCA) is presented. In the proposed approach, an outlier is set apart from an inlier by comparing their coherence with the rest of the data points. As inliers lie in a low dimensional subspace, they are likely to have strong mutual coherence provided there are enough inliers. By contrast, outliers do not typically admit low dimensional structures, wherefore an outlier is unlikely to bear strong resemblance with a large number of data points. As Coherence Pursuit only involves one simple matrix multiplication, it is significantly faster than the stat of-the-art robust PCA algorithms. We provide a mathematical analysis of the proposed algorithm under a random model for the distribution of the inliers and outliers. It is shown that the proposed method can recover the correct subspace even if the data is predominantly outliers. To the best of our knowledge, this is the first provable robust PCA algorithm that is simultaneously noniterative, can tolerate a large number of outliers and is robust to linearly dependent outliers.