The Pseudo-orthogonality for Graph $1$-Laplacian Eigenvectors and Applications to Higher Cheeger Constants and Data Clustering
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2021
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913534630166528 |
|---|---|
| author | Esposito, Antonio Corbo Piscitelli, Gianpaolo |
| author_facet | Esposito, Antonio Corbo Piscitelli, Gianpaolo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2103_16461 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | The Pseudo-orthogonality for Graph $1$-Laplacian Eigenvectors and Applications to Higher Cheeger Constants and Data Clustering Esposito, Antonio Corbo Piscitelli, Gianpaolo Analysis of PDEs 05C10, 47J10, 49R05 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. |
| title | The Pseudo-orthogonality for Graph $1$-Laplacian Eigenvectors and Applications to Higher Cheeger Constants and Data Clustering |
| topic | Analysis of PDEs 05C10, 47J10, 49R05 |
| url | https://arxiv.org/abs/2103.16461 |