212742
20190317000308.0
978-1-4799-9988-0
1520-6149
ISI
000388373404048
CONF
Accelerated Spectral Clustering Using Graph Filtering of Random Signals
New York
Ieee
2016
2016
5
Conference Papers
International Conference on Acoustics Speech and Signal Processing ICASSP
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.
graph signal processing
spectral clustering
Tremblay, Nicolas
242927
Puy, Gilles
179918
Borgnat, Pierre
Gribonval, RĂ©mi
240428
Vandergheynst, Pierre
120906
41st IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP 2016)
Shanghai, China
4094-4098
2016 Ieee International Conference On Acoustics, Speech And Signal Processing Proceedings
670957
http://infoscience.epfl.ch/record/212742/files/ICASSP_2016_lap.pdf
Preprint
Preprint
252392
LTS2
U10380
oai:infoscience.tind.io:212742
conf
STI
GLOBAL_SET
120906
120906
120906
120906
EPFL-CONF-212742
EPFL
REVIEWED
PUBLISHED
CONF