The Pseudo-orthogonality for Graph $1$-Laplacian Eigenvectors and Applications to Higher Cheeger Constants and Data Clustering

Abstract

The data clustering problem consists in dividing a data set into prescribed groups of homogeneous data. This is a 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 firstly 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)\le 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 $m_3(G)$, based on a generalized inverse power method.

arXiv comment28 pages

References in corpus (8)

• An Inverse Power Method for Nonlinear Eigenproblems with Applications in 1-Spectral Clustering and Sparse PCA
• Nodal Domains of Eigenvectors for $1$-Laplacian on Graphs
• On the second Dirichlet eigenvalue of some nonlinear anisotropic elliptic operators
• A sharp weighted anisotropic Poincaré inequality for convex domains
• On the higher Cheeger problem
• Cheeger $N$-clusters
• A nonlocal anisotropic eigenvalue problem
• Saturation phenomena for some classes of nonlinear nonlocal eigenvalue problems