Subspace Clustering via Tangent Cones

Amin Jalali, Rebecca Willett

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:

  1. Normalization: Data points are first projected onto a unit sphere.
  2. The Data Hull: The algorithm considers the convex hull of these normalized points.
  3. 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.
  4. 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$.
  5. 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.
  6. Spectral Clustering: Finally, this matrix is fed into standard spectral clustering to produce the final groups.
Geometric intuition of tangent cones and membership testing in CSC.

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.

Comparison of affinity matrices showing CSC's denser, cleaner block structure.

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

Abstract

Given samples lying on any of a number of subspaces, subspace clustering is the task of grouping the samples based on the their corresponding subspaces. Many subspace clustering methods operate by assigning a measure of affinity to each pair of points and feeding these affinities into a graph clustering algorithm. This paper proposes a new paradigm for subspace clustering that computes affinities based on the corresponding conic geometry. The proposed conic subspace clustering (CSC) approach considers the convex hull of a collection of normalized data points and the corresponding tangent cones. The union of subspaces underlying the data imposes a strong association between the tangent cone at a sample $x$ and the original subspace containing $x$. In addition to describing this novel geometric perspective, this paper provides a practical algorithm for subspace clustering that leverages this perspective, where a tangent cone membership test is used to estimate the affinities. This algorithm is accompanied with deterministic and stochastic guarantees on the properties of the learned affinity matrix, on the true and false positive rates and spread, which directly translate into the overall clustering accuracy.
BibTeX
@inproceedings{jalali2017subspace,
  author = {Amin Jalali and Rebecca Willett},
  title = {{Subspace Clustering via Tangent Cones}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
}
Figure