### Compressive Spectral Clustering

*combining graph signal processing
and compressed sensing to accelerate spectral clustering*

Given a set of N data points {x_1, x_2, ..., x_N}, spectral clustering (SC) partitions this set into k weakly inter-connected clusters. Several spectral clustering algorithms exist (see references of the litterature in our our paper) but all follow the same scheme. First, compute weights Wij > 0 that model the similarity between pairs of data points (x_i, x_j). This gives rise to a graph G with N nodes and adjacency matrix W. Second, compute the first k eigenvectors Uk := (u_1, ... ,u_k) of the Laplacian matrix L associated to G. And finally, run k-means using the rows of Uk as feature vectors to partition the N data points into k clusters.

We propose a

*compressive*spectral clustering method that accelerates the classical SC algorithm by bypassing both the exact partial diagonalisation of L and the k-means step at high dimension. It can be summarised as follows:

1) generate a feature vector for each node by filtering O(log(k)) random Gaussian signals on G;

2) sample O(k log(k)) nodes from the full set of nodes;

3) cluster the reduced set of nodes;

4) interpolate the cluster indicator vectors back to the complete graph.

We prove that our method, with a gain in computation time that can reach several orders of magnitude, is in fact an approximation of SC, for which we are able to control the error.

**Associated paper:**Nicolas Tremblay, Gilles Puy, RĂ©mi Gribonval, Pierre Vandergheynst.

*Compressive Spectral Clustering.*In

*ARXIV*, 1602.02018, 2016. [PDF]