Sparse spectral clustering method based on the incomplete Cholesky decomposition

A novel sparse spectral clustering method using linear algebra techniques is proposed. Spectral clustering methods solve an eigenvalue problem containing a graph Laplacian. The proposed method exploits the structure of the Laplacian to construct an approximation, not in terms of a low rank approximation but in terms of capturing the structure of the matrix. With this approximation, the size of the eigenvalue problem can be reduced. To obtain the indicator vectors from the eigenvectors the method proposed by Zha et al. (2002) 26], which computes a pivoted LQ$LQ$ factorization of the eigenvector matrix, is adapted. This formulation also gives the possibility to extend the method to out-of-sample points.