Large Scale Spectral Clustering with Landmark-Based Representation Xinlei Chen Deng Cai∗ State Key Lab of CAD&CG, College of Computer Science, Zhejiang University, China endernewton@gmail.com, dengcai@cad.zju.edu.cn Abstract Spectral clustering is one of the most popular cluster- ing approaches. Despite its good performance, it is lim- ited in its applicability to large-scale problems due to its high computational complexity. Recently, many ap- proaches have been proposed to accelerate the spectral clustering. Unfortunately, these methods usually sacri- fice quite a lot information of the original data, thus result in a degradation of performance. In this paper, we propose a novel approach, called Landmark-based Spectral Clustering (LSC), for large scale clustering problems. Specifically, we select p ( n) representa- tive data points as the landmarks and represent the orig- inal data points as the linear combinations of these land- marks. The spectral embedding of
