Graph Connectivity in Noisy Sparse Subspace Clustering
This addresses a critical bottleneck in subspace clustering for applications like computer vision and image processing, though it is incremental as it builds on existing theoretical guarantees.
The paper tackles the graph connectivity problem in noisy sparse subspace clustering by proposing a simple post-processing procedure that ensures consistent clustering under certain assumptions, achieving the first exact clustering guarantee for subspaces of dimension greater than 3.
Subspace clustering is the problem of clustering data points into a union of low-dimensional linear/affine subspaces. It is the mathematical abstraction of many important problems in computer vision, image processing and machine learning. A line of recent work (4, 19, 24, 20) provided strong theoretical guarantee for sparse subspace clustering (4), the state-of-the-art algorithm for subspace clustering, on both noiseless and noisy data sets. It was shown that under mild conditions, with high probability no two points from different subspaces are clustered together. Such guarantee, however, is not sufficient for the clustering to be correct, due to the notorious "graph connectivity problem" (15). In this paper, we investigate the graph connectivity problem for noisy sparse subspace clustering and show that a simple post-processing procedure is capable of delivering consistent clustering under certain "general position" or "restricted eigenvalue" assumptions. We also show that our condition is almost tight with adversarial noise perturbation by constructing a counter-example. These results provide the first exact clustering guarantee of noisy SSC for subspaces of dimension greater then 3.