Melia et al AISTATS 2001

Citation

Marina Melia and Jianbo Shi. 2001. A Random Walks View of Spectral Segmentation. In AISTATS 2001.

Online version

Available on Marina Melia's Website

Summary

This paper gives a general theoretical interpretation of a wide variety of spectral methods. The authors first present the general framework of normalized cuts. We assume we are given an index set $I$ and similarity matrix $S$ where entry $S_{ij}$ represents a similarity between item $i$ and item $j$. We then seek a partition of $I$ into two sets $A,{\overline {A}}$. Minimizing the following criteria:

$NCut(A,{\overline {A}})=\left({\frac {1}{Vol(A)}}+{\frac {1}{vol({\overline {A}})}}\right)\sum _{i\in A;j\in {\overline {A}}}S_{ij},$

where, for $C\subseteq I$ , we define:

$Vol(C)=\sum _{i\in C}\sum _{j\in I}S_{ij}.$