Abstract

The subspace segmentation problem is addressed in thispaper by effectively constructing an exactly block-diagonalsample affinity matrix. The block-diagonal structure isheavily desired for accurate sample clustering but is rather difficult to obtain. Most current state-of-the-art subspacesegmentation methods (such as SSC [4] and LRR [12]) resort to alternative structural priors (such as sparseness and low-rankness) to construct the affinity matrix. In this work, we directly pursue the block-diagonal structure by proposing a graph Laplacian constraint based formulation, andthen develop an efficient stochastic subgradient algorithm for optimization. Moreover, two new subspace segmentation methods, the block-diagonal SSC and LRR, are devisedin this work. To the best of our knowledge, this is the first research attempt to explicitly pursue such a block-diagonal structure. Extensive experiments on face clustering, motion segmentation and graph construction for semi-supervised learning clearly demonstrate the superiority of our novelly proposed subspace segmentation methods.