Fast convergence for spectral clustering

Over the last years computer vision researchers have shown great interest for the so called spectral clustering, where the data are clustered analysing the first few eigenvectors (i.e., the ones relative to the first eigenvalues) of a the Laplacian matrix, derived directly from the data-set. Note that for the purpose of data clustering the eigenvectors need not to be determined accurately. When clustering (segmenting) images the dimension of this matrix is large (e.g., an image as small as 100 x 100 results in a 10000 x 10000 matrix), and standard diagonalisation algorithms such Lanczos, necessary for determining the eigenvectors, do require a certain number of iterations: typically in the order of root n step for n x n matrices, and may take some iterations for getting close to the solutions. Here we report the first attempt using a recent diagonalisation algorithm (named APL) borrowed from the nuclear physics literature, that, among other properties, has the main advantage of obtaining in a small number of iteration steps eigenvectors, that even if not accurate, are good enough for performing a reasonable segmentation. In this sense we talk of fast convergence of spectral clustering. The experimental results obtained support this claim, and open the way to further work exploiting further detail of the algorithm not included in this study.