Small-world approximations in spectral segmentation

Spectral segmentation has been shown to produce perceptually meaningful groupings. The underlying similarity matrices are usually very large. Several approximations - deterministic and stochastic - are used in practice. The approximations usually use only local information. It has been shown recently that a few random long-range interactions facilitate emergence of structure in several domains like Ising models. We explore the use of longrange interactions in spectral segmentation.