Introduction to the Subspace Clustering Problem
Subspace clustering is the art of grouping high-dimensional data points based on the low-dimensional linear subspaces they inhabit. In fields like computer vision and signal processing, we often deal with high-dimensional data that actually lies on a "union of subspaces"—imagine a collection of points in 3D space that all sit on a few distinct 2D planes. To analyze this data, we first need to solve the subspace clustering problem: determining which point belongs to which plane.
For years, the state-of-the-art approach has been Sparse Subspace Clustering (SSC). SSC relies on "self-expression," representing each point as a sparse linear combination of others. However, SSC has a major Achilles' heel: graph connectivity. Because it seeks the sparsest possible representation, it often fails to create enough edges between points in the same subspace. This causes the resulting graph to break into disconnected components, leading spectral clustering algorithms to over-segment the data and split one true cluster into several.
This paper introduces Conic Subspace Clustering (CSC), a novel geometric approach that uses the tangent cones of the data's convex hull to build affinity matrices. Unlike sparse methods, CSC produces denser, more reliable connections within clusters, backed by rigorous theoretical guarantees.
The Geometric Approach: Conic Subspace Clustering
The authors pivot away from algebraic sparse coding and instead embrace convex geometry. Their CSC approach follows a distinct pipeline:
- Normalization: Data points are first projected onto a unit sphere.
- The Data Hull: The algorithm considers the convex hull of these normalized points.
- Tangent Cones: At each point $x$, the method examines the "tangent cone" (or descent cone) of the data hull. Geometrically, if another point $x'$ belongs to the same subspace as $x$, the ray pointing from $x$ toward $x'$ should be contained within this cone.
- Membership Testing: The authors develop a "Robust Cone Membership" (RCM) program. This linear optimization problem tests how well a point $x'$ fits into the tangent cone of $x$.
- Affinity Matrix: The results of these tests form an affinity matrix $A$, where $A(i,j)$ represents the likelihood that points $i$ and $j$ share a subspace.
- Spectral Clustering: Finally, this matrix is fed into standard spectral clustering to produce the final groups.
What makes CSC innovative is this shift to the geometric properties of tangent cones, providing a more robust way to measure "affinity" between points.
Key Insights and Theoretical Guarantees
While previous methods obsessed over sparsity, CSC embraces a "denser" affinity matrix. By ensuring more points within the same subspace are connected, it naturally sidesteps the graph connectivity issues that plague SSC.
The authors prove a "strong association" between the tangent cone of the data hull and the underlying subspace. This geometric insight allows them to derive deterministic conditions under which the algorithm is guaranteed to have zero false positives—meaning it will never connect points from different subspaces.
Furthermore, the algorithm uses a parameter $\beta$ to control the "reach" of the cone test. The paper provides a theoretical "sweet spot" for $\beta$ that perfectly balances a high true-positive rate with a zero false-positive rate. Under a "random-sample model," the authors show that CSC yields a fraction of true positives that stays bounded even as the number of samples grows, a scenario where SSC's performance often degrades.
Key Results and Visual Evidence
Because the paper focuses on establishing a strong theoretical foundation, the evaluation relies primarily on synthetic toy models designed to test specific geometric properties (e.g., $k=5$ subspaces of dimension $d=5$ in an $n=10$ dimensional ambient space).
In direct comparative benchmarks against SSC, CSC produces affinity matrices that are significantly better connected. It achieves higher true-positive rates while maintaining controlled false-positive rates.
The visual evidence is striking: the affinity matrices generated by CSC clearly show much cleaner, denser blocks compared to the noisy and sparse blocks of SSC. This structural clarity directly translates to much lower clustering mismatch rates.
Limitations and Future Work
While CSC represents a significant theoretical leap, the authors note a few limitations to be addressed in future work:
- Noiseless Assumption: The current theoretical framework assumes noiseless data. While empirical tests show stability against noise, a rigorous theoretical treatment of "Noisy CSC" is needed.
- Computational Complexity: Solving a linear program for every pair of points can be expensive. Although variations for faster computation are suggested, scaling this to massive datasets remains a challenge.
- Missing Data: The current framework requires complete data points. Extending CSC to handle missing entries or significant outliers remains an open question.
Summary updated