Pseudo-orthogonality for graph 1-Laplacian eigenvectors and applications to higher Cheeger constants and data clustering  

作　　者：Antonio Corbo ESPOSITO Gianpaolo PISCITELLI 

机构地区：[1]Dipartimento di Ingegneria Elettrica e dell’Informazione“M.Scarano”,Universitàdegli Studi di Cassino e del Lazio Meridionale,Via G.Di Biasio n.43,03043,Cassino(FR),Italy

出　　处：《Frontiers of Mathematics in China》2022年第4期591-623,共33页中国高等学校学术文摘·数学（英文）

基　　金：supported by the MiUR-Dipartimenti di Eccellenza 2018–2022 grant“Sistemi distribuiti intelligenti”of Dipartimento di Ingegneria Elettrica e dell’Informazione“M.Scarano”,by the MiSE-FSC 2014–2020 grant“SUMMa:Smart Urban Mobility Management”,and by GNAMPA of INdAM.The authors would also like to thank D.A.La Manna and V.Mottola for the helpful conversations during the starting stage of this work.

摘　　要：The data clustering problem consists in dividing a data set into prescribed groups of homogeneous data.This is an NP-hard problem that can be relaxed in the spectral graph theory,where the optimal cuts of a graph are related to the eigenvalues of graph 1-Laplacian.In this paper,we first give new notations to describe the paths,among critical eigenvectors of the graph 1-Laplacian,realizing sets with prescribed genus.We introduce the pseudo-orthogonality to characterize m_(3)(G),a special eigenvalue for the graph 1-Laplacian.Furthermore,we use it to give an upper bound for the third graph Cheeger constant h_(3)(G),that is,h_(3)(G)≤m_(3)(G).This is a first step for proving that the k-th Cheeger constant is the minimum of the 1-Laplacian Raylegh quotient among vectors that are pseudo-orthogonal to the vectors realizing the previous k−1 Cheeger constants.Eventually,we apply these results to give a method and a numerical algorithm to compute m3(G),based on a generalized inverse power method.

关 键 词：Graph 1-Laplacian graph Cheeger constants pseudo-orthogonality critical values data clustering 

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