Session B4 - Learning Theory
July 13, 15:30 ~ 15:55 - Room B6
Subspace Clustering via Tangent Cones
University of Wisconsin-Madison, USA - firstname.lastname@example.org
In this talk, I will describe a novel approach to subspace clustering called ``conic subspace clustering'' (CSC), which offers new insight into the geometry of subspace clustering. Like many other subspace clustering methods, it operates by first estimating the affinity between pairs of points, where the affinity is one if two points are in the same subspace and zero otherwise, and then applying an off-the-self clustering method to the learned affinities. The main novelty of the proposed approach lies in the estimation of pairwise affinities. Specifically, CSC considers the convex hull of a collection of data points and the tangent cones at each sample $x$. The union of subspaces underlying the data imposes a specific geometry on the convex hull, so that the tangent cone at a point $x$ has a strong association with the subspace containing $x$. This insight leads to a tangent cone membership test that can be used to estimate the affinity between $x$ and other points. In addition to describing this novel geometric perspective, this work provides deterministic and stochastic guarantees on the accuracy of the learned affinity matrix. More specifically, the test guarantees zero false positives and provides guarantees for any true positive rate. Furthermore, the true positive rate is potentially much larger than for competing methods that leverage sparsity regularization, which is particularly important in the presence of large numbers of samples from subspaces with complicated configurations. This increased true positive rate can be leveraged within an convex optimization formulation of the CSC affinity matrix estimation, leading to a computationally efficient algorithm.
Joint work with Amin Jalali (University of Wisconson-Madison).