A global-local affinity matrix model via EigenGap for graph-based subspace clustering

In this paper, we address the spectral clustering problem by effectively constructing an affinity matrix with a large EigenGap. Although the faultless Block-Diagonal structure is highly in demand for accurate spectral clustering, the relaxed Block-Diagonal affinity matrix with a large EigenGap is more effective and easier to obtain. A global EigenGap scheme is proposed by utilizing the Fractional Eigenvalues Sum (FEVS) penalty of maximizing top eigenvalues and minimizing the residual. The closed-form solution of the FEVS term and the proximity term is also presented. We then propose a Global-Local Affinity Matrix model that integrates the global EigenGap with local pairwise distance measure for graph construction. Furthermore, we also combine the state-of-the-art subspace recovery methods such as LRR and RSIM with our proposed model to learn an effective affinity matrix for high dimensional data. To the best of our knowledge, this is the first research that attempts to pursue such a relaxed Block-Diagonal structure with a large EigenGap. Extensive experiments on face clustering and motion segmentation clearly demonstrate the significant advantages of the novel methods.