cmjiang.github.io/fastge2.html at master · cmjiang/cmjiang.github.io · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
  "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<meta name="generator" content="jemdoc, see http://jemdoc.jaboc.net/" />
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<link rel="stylesheet" href="templates/jemdoc.css" type="text/css" />
<link rel="icon" href="templates/icon.jpg" />
<title>FAST-GE-2.0</title>
<!-- MathJax -->
<script type="text/javascript" src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
	  TeX: { equationNumbers: { autoNumber: "AMS" } }
});
</script>
<!-- End MathJax -->
</head>
<body>
<div id="layout-content">
<div id="toptitle">
<h1>FAST-GE-2.0</h1>
<div id="subtitle"> A robust and efficient generalized spectral method for constrained clustering.</div>
</div>
<h2>Description</h2>
<ul>
<li>
<p>FAST-GE-2.0 (see Ref.[1]) is a spectral method for constrained clustering. Following the idea of FAST-GE (see Ref.[2]), FAST-GE-2.0 incorporates the Must-Link and Cannot-Link constraints into two Laplacian \(L_G\) and \(L_H\) and solves a Rayleigh quotient optimization problem. Based on FAST-GE, FAST-GE-2.0 provides theoretical and computational solutions, i.e., robust and efficient computation of eigenspace.</p>
</li>
<li>
<p>We consider the optimization problem:</p>
<p style="text-align:center">
\begin{equation}\label{eq:rq}
\inf_{\substack{x\in \mathbb{R}^{n}\\ x^T L_H x > 0}} \frac{x^T L_G x}{x^T L_H x},
\end{equation}
</p>
<p>where \(L_G\) and \(L_H\) are symmetric positive semi-definite and the pencil \(L_G - \lambda L_H\) is singular, i.e., \(\det(L_G - \lambda L_H)\equiv 0\) for all \(\lambda\).
</p>
</li>
<li>
<p>Theoretically, the Courant-Fischer variational principle is generalized to the singular pencil \(L_G - \lambda L_H\), which proves that the infimum of the Rayleigh quotient \eqref{eq:rq} is obtainable. Problem \eqref{eq:rq} is subsequently converted into:</p>
<p style="text-align:center">
\begin{equation}\label{eq:eigLGLH}
L_Gx=\lambda L_H x.
\end{equation}
</p>
</li>
<li>
<p>Computationally, a spectral regularization is used to transform the singular pencil \(L_G - \lambda L_H\) into a positive definite pencil \(K - \sigma M\) where \(K\) and \(M\) are symmetric and \(M\) is positive definite. Specifically,</p>
<p style="text-align:center">
\begin{equation}\label{eq:GHnew}
K=-L_H
\quad \mbox{and} \quad
M= L_G +\mu L_H + ZSZ^T,
\end{equation}
</p>
<p>where \(Z \in \mathbb{R}^{n \times s}\) is an orthonormal basis of the common nullspace of \(L_G\) and \(L_H\). \(S\in \mathbb{R}^{s\times s}\) is an arbitrary positive definite matrix, and \(\mu\) is a positive scalar. Problem \eqref{eq:eigLGLH} is finally converted into the generalized symmetric definite eigenproblem:</p>
<p style="text-align:center">
\begin{equation}\label{eq:eigKM}
K x = \sigma M x.
\end{equation}
</p>
</li>
</ul>
<h2>Software</h2>
<ul>
<li>
<p><a href="https://github.com/cmjiang/lobpcgsr">Matlab code for the eigenvalue problem on GitHub</a></p>
</li>
<li>
<p><a href="https://github.com/cmjiang/FASTGE2">Matlab code for constrained image clustering on GitHub</a></p>
</li>
</ul>
<h2>Examples</h2>
<ul>
<li>Application on constrained image segmentation.
<p style="text-align:center;">
<img src="fastge2/ImgSeg.png" alt="Constrained Image Segmentation">
</p>
<p><center>
Fig: (a) Original Images,
(b) Constraints,
(c) Indicator Vector, <br />
(d) Renormalized Indicator Vector,
(e) Constrained Segmentation by FAST-GE-2.0.</center>  </p>
</li>
</ul>
<h2>References</h2>
<ol>
<li><p>Chengming Jiang, Huiqing Xie and Zhaojun Bai.
<b>Robust and efficient computation of eigenvectors in a generalized spectral method for constrained clustering</b>.
In <i>Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS 2017)</i>, PMLR 54:757&ndash;766, 2017.
(<a href="publications/aistats2017.pdf">preprint</a>, <a href="fastge2/aistats2017poster.pdf">poster</a>)</p></li>
<li><p>Mihai Cucuringu, Ioannis Koutis, Sanjay Chawla, Gary Miller and Richard Peng.
<b>Simple and scalable constrained clustering: A generalized spectral method</b>.
In <i>Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS 2016)</i>, pp. 445&ndash;454, 2016.</p></li>
</ol>
<h2>Contact</h2>
<ul>
<li> Email: cmjiang at ucdavis.edu</li>
<li> Homepage: <a href="http://cmjiang.cs.ucdavis.edu"> http://cmjiang.cs.ucdavis.edu </a>
</li>
</ul>
</div>
</body>
</html>