A Geometric Analysis of Subspace Clustering with Outliers

By M. Soltanolkotabi, E.J. Candes. arXiv.org, 2011

424 citations recorded by the source corpus.

This paper considers the problem of clustering a collection of unlabeled data points assumed to lie near a union of lower dimensional planes. As is common in computer vision or unsupervised learning applications, we do not know in advance how many subspaces there are nor do we have any information about their dimensions. We develop a novel geometric analysis of an algorithm named sparse subspace clustering (SSC) [11], which signicantly broadens the range of problems where it is provably eective. For instance, we show that SSC can recover multiple subspaces, each of dimension comparable to the ambient dimension. We also prove that SSC can correctly cluster data points even when the subspaces of interest intersect. Further, we develop an extension of SSC that succeeds when the data set is corrupted with possibly overwhelmingly many outliers. Underlying our analysis are clear geometric insights, which may bear on other sparse recovery problems. A numerical study complements our theoretical analysis and demonstrates the eectiveness of these methods.

Subfields: Computational Mechanics, Media Technology, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/b42dda210eb740631deb281bca79574805cd16cb

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Media Technology

In Statistics and Probability

Citations in the corpus

Sparse Subspace Clustering: Algorithm, Theory, and Applications (2013, positive): “Using advances in sparse [29], [30], [31] and low-rank [32], [33], [34] recovery algorithms, the Sparse Subspace Clustering (SSC) [35], [36], [37], Low-Rank Recovery (LRR) [38], [39], [40], and Low-Rank Subspace Clustering (LRSC) [41] algorithms pose the clustering problem as one of finding a sparse”
See all by looking at a few: Sparse modeling for finding representative objects (2012, background): “As data points with very small pairwise coherences may lead to too-close representatives, similar to sparse dictionary learning methods [1], one can prune the set of representatives from having too-close data points.”
Sparse Subspace Clustering: Algorithm, Theory, and Applications (2012, background): “Therefore, there is a need for having clustering algorithms that take into account the multisubspace structure of the data.”
Robust Subspace Clustering (2013, neutral): “The Annals of Statistics 2014, Vol. 42, No. 2, 669–699 DOI: 10.1214/13-AOS1199 © Institute of Mathematical Statistics, 2014”
Generalized Low Rank Models (2014, methodology): “her algorithms for this problem have also been proposed, such as the k-SVD [Tro04, AEB06] and sparse subspace clustering [EV09], some with provable guarantees on the quality of the recovered solution [SC12]. Supervised learning. Sometimes we want to understand the variation that a certain set of fea”
Multi-Task Learning for Subspace Segmentation (2015, background): “From a practical standpoint, based on theoretical analysis from (Elhamifar & Vidal, 2013; Mahdi & Candes, 2012), in certain cases as long as the angles between subspaces are not too small, then we can replace the NP-hard matrix ℓ0-norm minimization in (4) with ∥Z∥1 and still expect this same…”
Dual Principal Component Pursuit (2015, methodology): “Similarly to SE-RPCA, the performance of CoP is not expected to be significantly degraded as the number of outliers increases, as long as each outlier remains sufficiently incoherent with the rest of the dataset.”