Title :
Sparse kernel models for spectral clustering using the incomplete Cholesky decomposition
Author :
Alzate, Carlos ; Suykens, Johan A K
Author_Institution :
Dept. of Electr. Eng. ESATSCD-SISTA, Katholieke Univ. Leuven, Leuven
Abstract :
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.
Keywords :
approximation theory; computational complexity; matrix algebra; optimisation; pattern clustering; principal component analysis; set theory; computational complexity; constrained optimization framework; dual model representations; incomplete Cholesky decomposition; low-rank approximations; modified affinity matrix; primal model representations; reduced set method; sparse kernel models; spectral clustering; weighted kernel principal component analysis; Constraint optimization; Independent component analysis; Kernel; Large-scale systems; Least squares approximation; Matrix decomposition; Principal component analysis; Sparse matrices; Support vector machines; Training data;
Conference_Titel :
Neural Networks, 2008. IJCNN 2008. (IEEE World Congress on Computational Intelligence). IEEE International Joint Conference on
Conference_Location :
Hong Kong
Print_ISBN :
978-1-4244-1820-6
Electronic_ISBN :
1098-7576
DOI :
10.1109/IJCNN.2008.4634306