Coherence Pursuit: Fast, Simple, And Robust Subspace Recovery

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 stateof- 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.

Publication Date

1-1-2017

Publication Title

34th International Conference on Machine Learning, ICML 2017

Volume

6

Number of Pages

4388-4397

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

Socpus ID

85048586664 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/85048586664

This document is currently not available here.

Share

COinS