FAST-GE-2.0

Description

• 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.

• We consider the optimization problem:

  \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}

  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\).

• 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:

  \begin{equation}\label{eq:eigLGLH} L_Gx=\lambda L_H x. \end{equation}

• 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,

  \begin{equation}\label{eq:GHnew} K=-L_H \quad \mbox{and} \quad M= L_G +\mu L_H + ZSZ^T, \end{equation}

  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:

  \begin{equation}\label{eq:eigKM} K x = \sigma M x. \end{equation}

Software

• Matlab code for the eigenvalue problem on GitHub

• Matlab code for constrained image clustering on GitHub

Examples

• Application on constrained image segmentation.

  

  Fig: (a) Original Images, (b) Constraints, (c) Indicator Vector,
  (d) Renormalized Indicator Vector, (e) Constrained Segmentation by FAST-GE-2.0.

References

1. Chengming Jiang, Huiqing Xie and Zhaojun Bai. Robust and efficient computation of eigenvectors in a generalized spectral method for constrained clustering. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS 2017), PMLR 54:757–766, 2017. (preprint, poster)

2. Mihai Cucuringu, Ioannis Koutis, Sanjay Chawla, Gary Miller and Richard Peng. Simple and scalable constrained clustering: A generalized spectral method. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS 2016), pp. 445–454, 2016.

Contact

• Email: cmjiang at ucdavis.edu
• Homepage: http://cmjiang.cs.ucdavis.edu