Sparse Greedy Spectral Clustering and Kernel PCA

Marie Ouimet and Yoshua Bengio

Kernel methods such as Spectral Clustering and Kernel PCA are unsupervised learning algorithms that perform a non-linear dimensionality reduction. These methods are based on the eigen decomposition of a NXN matrix, where N is the number of examples. A greedy approximation of that matrix can be done in order to handle larger problems and accelerate computation. The idea is to approximate in the feature space some of the points by a linear combination of a subset of the N points.