212742
20190317000308.0
978-1-4799-9988-0
1520-6149
000388373404048
ISI
CONF
Accelerated Spectral Clustering Using Graph Filtering of Random Signals
New York
2016
Ieee
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
Puy, Gilles
179918
242927
Borgnat, Pierre
Gribonval, RĂ©mi
Vandergheynst, Pierre
120906
240428
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
Preprint
670957
Preprint
http://infoscience.epfl.ch/record/212742/files/ICASSP_2016_lap.pdf
LTS2
252392
U10380
oai:infoscience.tind.io:212742
STI
conf
GLOBAL_SET
120906
120906
120906
120906
EPFL-CONF-212742
EPFL
PUBLISHED
REVIEWED
CONF