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:
- 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.
- 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$.
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.
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