Spectral clustering: Difference between revisions

Revision as of 23:14, 12 February 2014

Revision as of 19:17, 13 February 2014

Line 28:

Alternatively to computiong just one eigenvector, ''k'' [[eigenvector]]s for some ''k'', are computed, and then another algorithm (e.g. [[k-means clustering]]) is used to cluster points by their respective ''k'' components in these eigenvectors.

An efficiency of spectral clustering may be improved if the solve of the corresponding eigenvalue problem is performed in a [[Matrix-free methods|matrix-free fashion]], i.e., without explicitly manipulating or even computing the similarity matrix, as, e.g., in the [[Lanczos algorithm]].

For large-size graphgraphs, the second eigenvalue of the (normalized) graph [[Laplacian matrix]] is often [[ill-conditioned]], leading to slow convergence of iterative eigenvalue solvers. [[Preconditioner#Preconditioning_for_eigenvalue_problems|Preconditioning]] is a key technology accelerating the convergence, e.g., in the matrix-free [[LOBPCG]] method.

Spectral clustering is closely related to [[Nonlinear dimensionality reduction]], and dimension reduction techniques such as locally-linear embedding can be used to reduce errors from noise or outliers.<ref>{{Citation