< Back to previous page


Fast Kernel Spectral Clustering

Journal Contribution - Journal Article

© 2017 Spectral clustering suffers from a scalability problem in both memory usage and computational time when the number of data instances N is large. To solve this issue, we present a fast spectral clustering algorithm able to effectively handle millions of datapoints at a desktop PC scale. The proposed technique relies on a kernel-based formulation of the spectral clustering problem, also known as kernel spectral clustering. In this framework, the Nyström approximation of the feature map of size m, with m ≪ N, is used to solve the primal optimization problem. This leads to a reduction of time complexity from O(N3) to O(mN) and space complexity from O(N2) to O(mN). The effectiveness of the proposed algorithm in terms of computational efficiency and clustering quality is illustrated on several datasets.
Journal: Neurocomputing
ISSN: 0925-2312
Volume: 268
Pages: 27 - 33
Publication year:2017
BOF-publication weight:2
CSS-citation score:1
Authors from:Higher Education