Noisy Sparse Subspace Clustering

Abstract

This paper considers the problem of subspace clustering under noise. Specifically, we study the behavior of Sparse Subspace Clustering (SSC) when either adversarial or random noise is added to the unlabelled input data points, which are assumed to be in a union of low-dimensional subspaces. We show that a modified version of SSC is \emph{provably effective} in correctly identifying the underlying subspaces, even with noisy data. This extends theoretical guarantee of this algorithm to more practical settings and provides justification to the success of SSC in a class of real applications.

Manuscript currently under review at journal of machine learning research. Previously conference version appeared at ICML'12, and was uploaded to ArXiv by the conference committee

References in corpus (4)

• High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
• A geometric analysis of subspace clustering with outliers
• Exact Subspace Segmentation and Outlier Detection by Low-Rank Representation
• Guess Who Rated This Movie: Identifying Users Through Subspace Clustering

Cited by in corpus (8)

• Constructing the L2-Graph for Robust Subspace Learning and Subspace Clustering
• Structured Sparse Subspace Clustering: A Joint Affinity Learning and Subspace Clustering Framework
• On Geometric Analysis of Affine Sparse Subspace Clustering
• Active Orthogonal Matching Pursuit for Sparse Subspace Clustering
• Symmetric low-rank representation for subspace clustering
• Robust Subspace Clustering via Tighter Rank Approximation
• Subspace Clustering by Block Diagonal Representation
• Revisiting data augmentation for subspace clustering