Laplace Matrix and Rayleigh quotient.

Matrix

refernece link

Laplace Matrix

• A Graph has adjacency matrix $W$ and degree matrix $D$, then its laplace matrix is
  

  $$L = D -W$$
  $W、D、L$ are all symmetric matrix.

• Laplace matrix has a property, for arbitrary vector $f$
  

  $$f^T L f = \frac{1}{2} \sum\limits_{i,j=1}^n \bigg( w_{ij} \Big( f(v_i) - f(v_j)\Big)^2 \bigg)$$
  Laplace matrix is symmetric semidefinite positive matrix.
  Laplace matrix is a kind of dissimilarity measure based on Euclidean distance.

Rayleigh quotient

• 普通Rayleigh quotient
  

  $$R(L, h) = \frac{h^TLh}{h^Th}$$

  This can be converted to a Lagrange Mutiplier question.
  

  $$max \ R(L,h) = max \ h^T L h \\ s.t. \ h^Th = c$$
  c is a constant.
  $h^Th$的值与最后结果无关
  $Simple \ Proof$.
  $\qquad$suppose $h_1^Th_1=1$, $h=kh_1$, then $h^Th=kh_1^T kh_1 = k^2$, 作除法之后总是能够消去$k$　。
  $\quad$
  $$\begin{align*} J(h) &= h^TLh - \lambda(h^Th - c) \\ \frac{ \partial J(h)}{ \partial h } &= 2Lh - 2\lambda h = 0\\ Lh &= \lambda h \end{align*}$$

求关于$h$的导数，使其为0, 得到$Lh = \lambda h$.所以，$R(L, h) = \lambda$.有结论
$R$的最大最小值分别对应矩阵$L$的最大最小特征值，$h$的解就是对应特征向量。

• generalized rayleigh quotient
  $$\begin{align*} R(L, h) &= \frac{h^TLh}{h^TDh} \\ Lh &= \lambda Dh \\ D^{ -\frac{1}{2} } LD^{ -\frac{1}{2} } D^{ \frac{1}{2} }h &= \lambda D^{ \frac{1}{2} }h \\ D^{ -\frac{1}{2} }LD^{ -\frac{1}{2} }z &= \lambda z \end{align*}$$
  Converted to the normal rayleigh quotient form
  $$R(M, z) = \frac{z^TMz}{z^Tz}$$
  that
  $$\begin{align*} M &= D^{ -\frac{1}{2} }LD^{ -\frac{1}{2} } \\ z &= D^{ \frac{1}{2} }h \end{align*}$$