|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'500'096
Articles rated: 2609
18 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
A Note On Spectral Clustering | | Pavel Kolev
; Kurt Mehlhorn
; | | Date: |
30 Sep 2015 | | Abstract: | Let $G=(V,E)$ be an undirected graph, $lambda_k$ the $k$th smallest
eigenvalue of the normalized Laplacian matrix of $G$, and $
ho(k)$ the
smallest value of the maximal conductance over all $k$-way partitions
$S_1,dots,S_k$ of $V$.
Peng et al. [PSZ15] gave the first rigorous analysis of $k$-clustering
algorithms that use spectral embedding and $k$-means clustering algorithms to
partition the vertices of a graph $G$ into $k$ disjoint subsets. Their analysis
builds upon a gap parameter $Upsilon=
ho(k)/lambda_{k+1}$ that was
introduced by Oveis Gharan and Trevisan [GT14]. In their analysis Peng et al.
[PSZ15] assume a gap assumption $UpsilongeqOmega(mathrm{APR}cdot k^3)$,
where $mathrm{APR}>1$ is the approximation ratio of a $k$-means clustering
algorithm.
We exhibit an error in one of their Lemmas and provide a correction. With the
correction the proof by Peng et al. [PSZ15] requires a stronger gap assumption
$UpsilongeqOmega(mathrm{APR}cdot k^4)$.
Our main contribution is to improve the analysis in [PSZ15] by an $O(k)$
factor. We demonstrate that a gap assumption $Psigeq Omega(mathrm{APR}cdot
k^3)$ suffices, where $Psi=
ho_{avr}(k)/lambda_{k+1}$ and $
ho_{avr}(k)$ is
the value of the average conductance of a partition $S_1,dots,S_k$ of $V$ that
yields $
ho(k)$. | | Source: | arXiv, 1509.9188 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER