Difference between revisions of "Melia et al AISTATS 2001"
From Cohen Courses
Jump to navigationJump to search| Line 10: | Line 10: | ||
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 <math>I</math> and similarity matrix <math>S</math> where entry <math>S_{ij}</math> represents a similarity between item <math>i</math> and item <math>j</math>. We then seek a partition of <math>I</math> into two sets <math>A,\overline{A}</math>. Minimizing the following criteria: | 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 <math>I</math> and similarity matrix <math>S</math> where entry <math>S_{ij}</math> represents a similarity between item <math>i</math> and item <math>j</math>. We then seek a partition of <math>I</math> into two sets <math>A,\overline{A}</math>. Minimizing the following criteria: | ||
| − | |||
<math> | <math> | ||
| − | 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} | + | 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}, |
| + | </math> | ||
| − | + | where, for <math>X \subseteq I<\math>, we define: | |
| + | <math> | ||
| + | Vol(X) = \sum_{i \in X} \sum_{j\in I} S_{ij}. | ||
</math> | </math> | ||
== Related papers == | == Related papers == | ||
Revision as of 12:58, 4 February 2011
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 and similarity matrix where entry represents a similarity between item and item . We then seek a partition of into two sets . Minimizing the following criteria:
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}. }
