Outlier Detection and Data Clustering via Innovation Search
arXiv:1912.12988
Abstract
The idea of Innovation Search was proposed as a data clustering method in which the directions of innovation were utilized to compute the adjacency matrix and it was shown that Innovation Pursuit can notably outperform the self representation based subspace clustering methods. In this paper, we present a new discovery that the directions of innovation can be used to design a provable and strong robust (to outlier) PCA method. The proposed approach, dubbed iSearch, uses the direction search optimization problem to compute an optimal direction corresponding to each data point. iSearch utilizes the directions of innovation to measure the innovation of the data points and it identifies the outliers as the most innovative data points. Analytical performance guarantees are derived for the proposed robust PCA method under different models for the distribution of the outliers including randomly distributed outliers, clustered outliers, and linearly dependent outliers. In addition, we study the problem of outlier detection in a union of subspaces and it is shown that iSearch provably recovers the span of the inliers when the inliers lie in a union of subspaces. Moreover, we present theoretical studies which show that the proposed measure of innovation remains stable in the presence of noise and the performance of iSearch is robust to noisy data. In the challenging scenarios in which the outliers are close to each other or they are close to the span of the inliers, iSearch is shown to remarkably outperform most of the existing methods. The presented method shows that the directions of innovation are useful representation of the data which can be used to perform both data clustering and outlier detection.
References in corpus (15)
- A Simpler Approach to Matrix Completion
- A geometric analysis of subspace clustering with outliers
- Robust PCA via Outlier Pursuit
- Optimal Algorithms for -subspace Signal Processing
- Outlier detection for patient monitoring and alerting
- Coherence Pursuit: Fast, Simple, and Robust Principal Component Analysis
- An Overview of Robust Subspace Recovery
- A Novel M-Estimator for Robust PCA
- Greedy Subspace Clustering
- Innovation Pursuit: A New Approach to Subspace Clustering
- Identifying Outliers in Large Matrices via Randomized Adaptive Compressive Sampling
- Fast, Robust and Non-convex Subspace Recovery
- Log-based Anomaly Detection of CPS Using a Statistical Method
- Recovery of Coherent Data via Low-Rank Dictionary Pursuit
- Subspace Clustering via Optimal Direction Search