On Geometric Analysis of Affine Sparse Subspace Clustering

Abstract

Sparse subspace clustering (SSC) is a state-of-the-art method for segmenting a set of data points drawn from a union of subspaces into their respective subspaces. It is now well understood that SSC produces subspace-preserving data affinity under broad geometric conditions but suffers from a connectivity issue. In this paper, we develop a novel geometric analysis for a variant of SSC, named affine SSC (ASSC), for the problem of clustering data from a union of affine subspaces. Our contributions include a new concept called affine independence for capturing the arrangement of a collection of affine subspaces. Under the affine independence assumption, we show that ASSC is guaranteed to produce subspace-preserving affinity. Moreover, inspired by the phenomenon that the ${\ell }_1$ regularization no longer induces sparsity when the solution is nonnegative, we further show that subspace-preserving recovery can be achieved under much weaker conditions for all data points other than the extreme points of samples from each subspace. In addition, we confirm a curious observation that the affinity produced by ASSC may be subspace-dense---which could guarantee the subspace-preserving affinity of ASSC to produce correct clustering under rather weak conditions. We validate the theoretical findings on carefully designed synthetic data and evaluate the performance of ASSC on several real data sets.

arXiv comment15 pages, 6 figures, 2 tables. To appear on IEEE Journal of Selected Topics in Signal Processing

References in corpus (10)

• Robust Recovery of Subspace Structures by Low-Rank Representation
• The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices
• A geometric analysis of subspace clustering with outliers
• Structured Sparse Subspace Clustering: A Joint Affinity Learning and Subspace Clustering Framework
• Robust subspace clustering
• Sparse projections onto the simplex
• Greedy Subspace Clustering
• Noisy Sparse Subspace Clustering
• Algebraic Clustering of Affine Subspaces
• Methods for Sparse and Low-Rank Recovery under Simplex Constraints

Cited by in corpus (12)

• Efficient Solvers for Sparse Subspace Clustering
• A Unified NMPC Scheme for MAVs Navigation with 3D Collision Avoidance under Position Uncertainty
• A Critique of Self-Expressive Deep Subspace Clustering
• Self-Supervised Convolutional Subspace Clustering Network
• Beyond Linear Subspace Clustering: A Comparative Study of Nonlinear Manifold Clustering Algorithms
• Basis Pursuit and Orthogonal Matching Pursuit for Subspace-preserving Recovery: Theoretical Analysis
• Stochastic Sparse Subspace Clustering
• Revisiting data augmentation for subspace clustering
• Is an Affine Constraint Needed for Affine Subspace Clustering?
• Weighted Sparse Subspace Representation: A Unified Framework for Subspace Clustering, Constrained Clustering, and Active Learning
• Multi-view Subspace Clustering via Partition Fusion
• Learning a Self-Expressive Network for Subspace Clustering