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: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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}\\ Vol(X) = \sum_{i \in X} \sum_{j\in I} S_{ij} }