Provable Subspace Clustering: When LRR meets SSC

Yu-Xiang Wang, Huan Xu, Chenlei Leng

Introduction

Subspace clustering is the task of grouping data points that lie near a union of low-dimensional subspaces. Imagine a dataset containing motion trajectories of different moving objects; each object's motion lives in its own distinct "subspace."

Two state-of-the-art methods currently dominate this field, but each comes with significant limitations:

  1. Sparse Subspace Clustering (SSC): This method uses the $\ell_1$ norm to find the sparsest representation of data. While excellent at separating points from different subspaces, it often produces "too sparse" results, leading to disconnected clusters—a critical flaw known as the "graph connectivity" problem.
  2. Low-Rank Representation (LRR): LRR uses the nuclear norm to find the lowest-rank representation. It ensures well-connected clusters but typically requires the subspaces to be strictly "independent." This restrictive assumption fails when subspaces overlap or are highly correlated.

This paper introduces Low-Rank Sparse Subspace Clustering (LRSSC), a hybrid algorithm designed to bridge the gap between these two approaches. By simultaneously promoting sparsity and low-rank structures, LRSSC achieves the clean data separation of SSC while maintaining the robust cluster connectivity of LRR.

The LRSSC Approach

To capture the best of both worlds, the authors propose solving a convex optimization problem that minimizes a weighted sum of the nuclear norm (promoting low-rankness) and the $\ell_1$ norm (promoting sparsity):

$$\min_{C} \|C\|_* + \lambda \|C\|_1 \quad \text{s.t.} \quad X = XC, \text{diag}(C) = 0$$

Here, $X$ is the data matrix and $C$ is the representation matrix used to build a similarity graph for spectral clustering. The parameter $\lambda$ controls the trade-off between the two norms.

Key Innovations: * Theoretical Framework: The authors provide a dual-optimization analysis to prove when the "Self-Expressiveness Property" (SEP) holds. SEP means the algorithm correctly represents a point using only other points from the same subspace. * New Incoherence Measure: They introduce a "minimax subspace incoherence" metric that is tighter than previous measures, allowing them to prove success in cases where previous theories for SSC would have predicted failure. * Tractable Guarantees: Unlike previous conditions for SSC which were NP-hard to verify, the new conditions for LRSSC are based on singular values, making them computationally tractable. * ADMM Solver: To make the algorithm practical for large datasets, they derive a fast numerical solver based on the Alternating Direction Method of Multipliers (ADMM).

Balancing Separation and Connectivity

There is a fundamental tension in subspace clustering between inter-class separation (avoiding links between points in different groups) and intra-class connectivity (ensuring all points in the same group are linked). LRSSC allows researchers to tune this balance via the parameter $\lambda$.

Trade-off between Relative Violation and Sparsity

As $\lambda$ increases, the algorithm behaves more like pure SSC. The authors demonstrate that SSC is actually a special case of LRSSC as $\lambda \to \infty$. However, pure sparsity can miss critical connections, especially in "skewed" data distributions where points are not uniformly spread within a subspace. By incorporating the nuclear norm, LRSSC "fills in" the gaps that pure sparsity would miss, handling poorly represented subspaces much better than pure SSC or LRR.

Key Results and Model Selection

Numerical experiments reveal a clear phase transition and a "sweet spot" for $\lambda$ where the algorithm achieves perfect separation (SEP) while maintaining a dense enough graph to ensure all points in a cluster are connected.

Spectral Gap and Model Selection Sweet Spot

In experiments with skewed data, LRSSC significantly outperformed both LRR and SSC in "model selection"—the ability to correctly identify the number of underlying subspaces using spectral gap heuristics. While LRR guarantees connectivity only if subspaces are independent, numerical results show that LRSSC maintains high connectivity even when this independence assumption is violated.

Limitations and Future Work

While the paper provides strong mathematical proofs for the separation property (SEP), the connectivity property is largely demonstrated through simulations and intuition. Defining and proving connectivity for LRSSC mathematically remains an open challenge. Additionally, while $\lambda$ provides powerful flexibility, choosing the optimal $\lambda$ for a completely unknown dataset remains a practical hurdle. Finally, while a version of the algorithm for noisy data is proposed, the full theoretical proof of its guarantees is left for future research.

Summary updated

Abstract

Sparse Subspace Clustering (SSC) and Low-Rank Representation (LRR) are both considered as the state-of-the-art methods for {\em subspace clustering}. The two methods are fundamentally similar in that both are convex optimizations exploiting the intuition of Self-Expressiveness''. The main difference is that SSC minimizes the vector $\ell_1$ norm of the representation matrix to induce sparsity while LRR minimizes nuclear norm (aka trace norm) to promote a low-rank structure. Because the representation matrix is often simultaneously sparse and low-rank, we propose a new algorithm, termed Low-Rank Sparse Subspace Clustering (LRSSC), by combining SSC and LRR, and develops theoretical guarantees of when the algorithm succeeds. The results reveal interesting insights into the strength and weakness of SSC and LRR and demonstrate how LRSSC can take the advantages of both methods in preserving the "Self-Expressiveness Property'' and "Graph Connectivity'' at the same time."
BibTeX
@inproceedings{wang2013provable,
  author = {Yu-Xiang Wang and Huan Xu and Chenlei Leng},
  title = {{Provable Subspace Clustering: When LRR meets SSC}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=ry-iRuZdZB},
}
Figure