Author:

Keywords:

_none

Abstract:

A new sparse spectral clustering method using linear algebra techniques is proposed. This method exploits the structure of the Laplacian to construct its approximation, not in terms of a low rank approximation but in terms of capturing the structure of the matrix. The approximation is based on the incomplete Cholesky decomposition with an adapted stopping criterion, it selects a sparse data set which is a good representation of the full data set. With this approximation the eigenvalue problem can be reduced to a smaller problem. To obtain the indicator vectors from the eigenvectors the method proposed by [Zha et al., Spectral relaxation for k-means clustering ] is adapted, which computes a pivoted LQ factorization of the eigenvector matrix. This formulation gives also the possibility to extend the method to out-of-sample points.