scikit-learn/scikit-learn — pull request #659 by jakevdp (2012-02-29 08:08:59+00:00)
Title: ENH: use shift-invert in spectral clustering

This enhancement speeds up the spectral clustering by a significant factor when using arpack. On my box, it speeds the plot_lena_segmentation.py example from ~200sec to ~30sec.

This enhancement is based on the fact (?) that for a normalized laplacian matrix ``L``, the largest eigenvalue of ``I - L`` is 1.0. I believe this is correct, but I'd feel better if someone could confirm that property!