Perturbation analysis for the normalized Laplacian matrices in the multiway spectral clustering method  

作　　者：BORJIGIN SuMuYa GUO ChongHui 

机构地区：[1]School of Economics and Management, Inner Mongolia University [2]Institute of Systems Engineering, Dalian University of Technology

出　　处：《Science China(Information Sciences)》2014年第11期25-41,共17页中国科学（信息科学）（英文版）

基　　金：supported by National Natural Science Foundation of China(Grant Nos.71171030,71031002);the Program for New Century Excellent Talents in University(Grant No.NCET-11-0050);the Program for Innovative Research Team in University(Grant No.IRT1258);Natural Science Foundation of InnerMongolia(Grant No.2014BS0706);and the Program of Higher-Level Talents of Inner Mongolia University(Grant No.SPH-IMU-125116)

摘　　要：In this paper, we present a perturbation analysis for the matrices in the multiway normalized cut spectral clustering method based on the matrix perturbation theory. The analytical results show that the eigenvalues and the eigenspaces of the normalized Laplacian matrices are continuous. Therefore, clustering algorithms can be designed according to the special properties of the normalized Laplacian matrices in the ideal case and the method can be extended to the general case based on the continuity of the eigenvalues and the eigenspaces of the normalized Laplacian matrices. The numerical results are consistent with the theoretical results.In this paper, we present a perturbation analysis for the matrices in the multiway normalized cut spectral clustering method based on the matrix perturbation theory. The analytical results show that the eigenvalues and the eigenspaces of the normalized Laplacian matrices are continuous. Therefore, clustering algorithms can be designed according to the special properties of the normalized Laplacian matrices in the ideal case and the method can be extended to the general case based on the continuity of the eigenvalues and the eigenspaces of the normalized Laplacian matrices. The numerical results are consistent with the theoretical results.

关 键 词：spectral clustering method normalized Laplacian matrices EIGENVALUE EIGENSPACE matrix perturbation theory 

分 类 号：O177[理学—数学]