Coherence Pursuit: Fast, Simple, And Robust Principal Component Analysis

Keywords

Big Data; Outlier Detection; Robust PCA; Subspace Recovery; Unsupervised Learning

Abstract

This paper presents a remarkably simple, yet powerful, algorithm termed coherence pursuit (CoP) to robust principal component analysis (PCA). As inliers lie in a low-dimensional subspace and are mostly correlated, an inlier is likely to have strong mutual coherence with a large number of data points. By contrast, outliers either do not admit low-dimensional structures or form small clusters. In either case, an outlier is unlikely to bear strong resemblance to a large number of data points. Given that, CoP sets an outlier apart from an inlier by comparing their coherence with the rest of the data points. The mutual coherences are computed by forming the Gram matrix of the normalized data points. Subsequently, the sought subspace is recovered from the span of the subset of the data points that exhibit strong coherence with the rest of the data. As CoP only involves one simple matrix multiplication, it is significantly faster than the state-of-the-art robust PCA algorithms.We derive analytical performance guarantees for CoP under different models for the distributions of inliers and outliers in both noise-free and noisy settings. CoP is the first robust PCA algorithm that is simultaneously non-iterative, provably robust to both unstructured and structured outliers, and can tolerate a large number of unstructured outliers.

Publication Date

12-1-2017

Publication Title

IEEE Transactions on Signal Processing

Volume

65

Issue

23

Number of Pages

6260-6275

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/TSP.2017.2749215

Socpus ID

85029161360 (Scopus)

Source API URL

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

This document is currently not available here.

Share

COinS