Affinity matrix with large eigenvalue gap for graph-based subspace clustering and semi-supervised classification

In the graph-based learning method, the data graph or similarity matrix reveals the relationship between data, and reflects similar attributes within a class and differences between classes. Inspired by Davis–Kahan Theorem that the stability of matrix eigenvector space depends on its spectral distance (i.e. its eigenvalue gap), in this paper, we propose a global local affinity matrix model with low rank subspace sparse representation (GLAM-LRSR) based on global information of eigenvalue gap and local distance between samples. This method approximate the similarity matrix with ideally diagonal block structure from the perspective of maximizing the eigenvalue gap, and the local distance between data is utilized as a regular term to prevent the eigenvalue gap from being too large to ensure the efficacy of similarity matrix. We have shown that the combination of subspace (LRSR) partitioning method such as Sparse Subspace Clustering(SSC) and the similarity matrix constructed by GLAM can improve the accuracy of subspace clustering, and that the similarity matrix constructed by GLAM-LRSR can be successfully applied to graph-based semi-supervised classification task. Our experiments on synthetic data as well as the real-world datasets for face clustering, face recovery and motion segmentation have clearly demonstrate the significant advantages of GLAM-LRSR and its effectiveness.