Published in

2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)

DOI: 10.1109/icassp.2016.7472447

Links

Tools

Export citation

Search in Google Scholar

Accelerated spectral clustering using graph filtering of random signals

Journal article published in 2016 by Nicolas Tremblay, Gilles Puy, Pierre Borgnat, Remi Gribonval, Pierre Vandergheynst
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Upload
Green circle
Postprint: archiving allowed
Upload
Red circle
Published version: archiving forbidden
Policy details
Data provided by SHERPA/RoMEO

Abstract

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.