Improving K-Subspaces via Coherence Pursuit

Published In

IEEE Journal of Selected Topics in Signal Processing

Document Type

Citation

Publication Date

12-1-2018

Abstract

Subspace clustering is a powerful generalization of clustering for high-dimensional data analysis, where low-rank cluster structure is leveraged for accurate inference. K-Subspaces (KSS), an alternating algorithm that mirrors K-means, is a classical approach for clustering with this model. Like K-means, KSS is highly sensitive to initialization, yet KSS has two major handicaps beyond this issue. First, unlike K-means, the KSS objective is NP-hard to approximate within any finite factor for large enough subspace rank. Second, it is known that the l2 subspace estimation step is faulty when an estimated cluster has points from multiple subspaces. In this paper we demonstrate both of these additional drawbacks, provide a proof for the former, and offer a solution to the latter through the use of a robust subspace recovery (RSR) method known as Coherence Pursuit (CoP). While many RSR methods have been developed in recent years, few can handle the case where the outliers are themselves low rank. We prove that CoP can handle low-rank outliers. This and its low computational complexity make it ideal to incorporate into the subspace estimation step of KSS. We demonstrate on synthetic data that CoP successfully rejects low-rank outliers and show that combining Coherence Pursuit with K-Subspaces yields state-of-the-art clustering performance on canonical benchmark datasets.

DOI

10.1109/JSTSP.2018.2869363

Persistent Identifier

https://archives.pdx.edu/ds/psu/27907

Share

COinS