English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  A Note On Spectral Clustering

Kolev, P., & Mehlhorn, K. (2015). A Note On Spectral Clustering. Retrieved from http://arxiv.org/abs/1509.09188.

Item is

Files

show Files
hide Files
:
arXiv:1509.09188.pdf (Preprint), 251KB
Name:
arXiv:1509.09188.pdf
Description:
File downloaded from arXiv at 2015-10-05 12:52
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
:
1509.09188v3.pdf (Preprint), 353KB
Name:
1509.09188v3.pdf
Description:
Version 3
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Kolev, Pavel1, Author           
Mehlhorn, Kurt1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: Computer Science, Discrete Mathematics, cs.DM
 Abstract: Let $G=(V,E)$ be an undirected graph, $\lambda_k$ the $k$th smallest eigenvalue of the normalized Laplacian matrix of $G$, and $\rho(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=\rho(k)/\lambda_{k+1}$ that was introduced by Oveis Gharan and Trevisan [GT14]. In their analysis Peng et al. [PSZ15] assume a gap assumption $\Upsilon\geq\Omega(\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 $\Upsilon\geq\Omega(\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 $\Psi\geq \Omega(\mathrm{APR}\cdot k^3)$ suffices, where $\Psi=\rho_{avr}(k)/\lambda_{k+1}$ and $\rho_{avr}(k)$ is the value of the average conductance of a partition $S_1,\dots,S_k$ of $V$ that yields $\rho(k)$.

Details

show
hide
Language(s): eng - English
 Dates: 2015-09-302016-01-072015
 Publication Status: Published online
 Pages: 31 p.
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 1509.09188
URI: http://arxiv.org/abs/1509.09188
BibTex Citekey: KolevArXiv2015
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show