Sparse kernel models for spectral clustering using the incomplete Cholesky decomposition

A new sparse kernel model for spectral clustering is presented. This method is based on the incomplete Cholesky decomposition and can be used to efficiently solve large-scale spectral clustering problems. The formulation arises from a weighted kernel principal component analysis (PCA) interpretation of spectral clustering. The interpretation is within a constrained optimization framework with primal and dual model representations allowing the clustering model to be extended to out-of-sample points. The incomplete Cholesky decomposition is used to compute low-rank approximations of a modified affinity matrix derived from the data which contains cluster information. A reduced set method is also presented to compute efficiently the cluster indicators for out-of-sample data. Simulation results with large-scale toy datasets and images show improved performance in terms of computational complexity.