Title: Block-Diagonal Structure Learning for Subspace Clustering. Abstract: Finding the informative subspaces of high-dimensional ordered datasets is at the core of innumerable applications in computer vision, where spectral-based subspace clustering is arguably the most commonly studied method due to its strong empirical performance. Such algorithms compute an affinity matrix to construct a self-representation for each sample utilizing other samples as a dictionary, and spectral clustering is employed to identify the clustering structure based on the affinity matrix. Since the ordered nature, the block-diagonal structure learning embedded in self-representation plays a vital role in effective subspace clustering. However, direct optimization with block-diagonal priors is challenging due to the random sparseness and connectivity nature of self-representation, and none of the existing techniques resort to the block-diagonal structure learning of self-representation alone. In this paper, we propose a technique, namely block-diagonal structure representation learning, to solve the optimal clustering of the ordered data directly instead of employing spectral clustering. The proposed algorithm can theoretically achieve the global optimal solution of the proposed discrete non-convex block-diagonal partition problem. We test the proposed clustering method on several types of segmentation databases, such as human face recognization, video scene clip partition, motion tracks, and dynamic 3-D facial expression sequences. The experiments illustrate that the proposed method outperforms state-of-the-art subspace clustering methods. 

