TY - CPAPER
AB - We build upon recent advances in graph signal processing to propose a faster spectral clustering algorithm. Indeed, classical spectral clustering is based on the computation of the first $k$ eigenvectors of the similarity matrix' Laplacian, whose computation cost, even for sparse matrices, becomes prohibitive for large datasets. We show that we can estimate the spectral clustering distance matrix without computing these eigenvectors: by graph filtering random signals. Also, we take advantage of the stochasticity of these random vectors to estimate the number of clusters $k$. We compare our method to classical spectral clustering on synthetic data, and show that it reaches equal performance while being faster by a factor at least two for large datasets.
T1 - Accelerated Spectral Clustering Using Graph Filtering of Random Signals
DA - 2016
AU - Tremblay, Nicolas
AU - Puy, Gilles
AU - Borgnat, Pierre
AU - Gribonval, RĂ©mi
AU - Vandergheynst, Pierre
JF - 2016 Ieee International Conference On Acoustics, Speech And Signal Processing Proceedings
SP - 4094-4098
EP - 4094-4098
PB - Ieee
PP - New York
ID - 212742
KW - graph signal processing
KW - spectral clustering
SN - 978-1-4799-9988-0
SN - 1520-6149
UR - http://infoscience.epfl.ch/record/212742/files/ICASSP_2016_lap.pdf
ER -