Abstract

Subspace clustering refers to the problem of segmenting data drawn from a union of subspaces. State of the art approaches for solving this problem follow a two-stage approach. In the fifirst step, an affifinity matrix is learned from the data using sparse or low-rank minimization techniques. In the second step, the segmentation is found by applying spectral clustering to this affifinity. While this approach has led to state of the art results in many applications, it is suboptimal because it does not exploit the fact that the affifinity and the segmentation depend on each other. In this paper, we propose a unifified optimization framework for learning both the affifinity and the segmentation. Our framework is based on expressing each data point as a structured sparse linear combination of all other data points, where the structure is induced by a norm that depends on the unknown segmentation. We show that both the segmentation and the structured sparse representation can be found via a combination of an alternating direction method of multipliers with spectral clustering. Experiments on a synthetic data set, the Hopkins 155 motion segmentation database, and the Extended Yale B data set demonstrate the effectiveness of our approach