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 Failed to parse (unknown function "\math"): {\displaystyle X \subseteq I<\math>, we define: <math> Vol(X) = \sum_{i \in X} \sum_{j\in I} S_{ij}. }