Courant-Fischer定理、谱图分析和图的分割

一、Courant-Fischer定理

“In linear algebra and functional analysis, the min-max theorem, or variational theorem, or Courant–Fischer–Weyl min-max principle, is a result that gives a variational characterization of eigenvalues of compact Hermitian operators on Hilbert spaces. It can be viewed as the starting point of many results of similar nature.”
——https://en.wikipedia.org/wiki/Min-max_theorem
讲的是Courant–Fischer–Weyl min-max principle（最小-最大定理）给出了一个关于Hermitian矩阵特征值的变分特性描述。以下是该定理的一个推导：
1、Hermitian矩阵 $\mathbf{H}$ 定义：
具有以下特性的矩阵，被称为Hermitian矩阵：
$$\mathbf{H}={\mathbf{H}}^{\ast }\text{, where H∗=HˉT}(1)$$
${\mathbf{H}}^{\ast }$ 是 $\mathbf{H}$ 的共轭转置，即$\mathbf{H}$ 与它的共轭转置矩阵 ${\mathbf{H}}^{\ast }$ 相等。若 $\mathbf{H}$ 为实数阵，则有$\mathbf{H}={\mathbf{H}}^{\ast }={\mathbf{H}}^T$，即实对称阵为Hermitian矩阵。
2、Hermitian矩阵 $\mathbf{H}$ 的性质
性质1：
若A是H矩阵（Hermitian矩阵，简称为H矩阵），对于任意向量 $\mathbf{x}\in {\mathbb{C}}^n$，${\mathbf{x}}^{T}A\mathbf{x}$ 是实数。
性质2：
H矩阵的特征值皆为实数。
性质3：
H矩阵相异特征值对应的特征向量互为正交。
Rayleigh Quotient (Rayleigh商, R)定义：
$$R=\frac{{\mathbf{x}}^{\ast }\mathbf{A}\mathbf{x}}{{\mathbf{x}}^{\ast }\mathbf{x}}(2)$$
Courant-Fischer便是讨论 Rayleigh Quotient 的界问题。
命题1：
设$\mathbf{A}$是形状为 $n\times n$ 的 $\mathbf{H}$ 矩阵，它的特征值（eigenvalues）皆为实数，设为 ${\lambda }_1\ge {\lambda }_2\cdots \ge {\lambda }_n$，则有：
$$\{\begin{array}{c}{\max }_{x̸=0}\frac{{\mathbf{x}}^{\ast }\mathbf{A}\mathbf{x}}{{\mathbf{x}}^{\ast }\mathbf{x}}={\lambda }_1\\ \\ {\min }_{x̸=0}\frac{{\mathbf{x}}^{\ast }\mathbf{A}\mathbf{x}}{{\mathbf{x}}^{\ast }\mathbf{x}}={\lambda }_n\end{array}(3)$$
即Rayleigh商的上界是最大特征值（${\lambda }_1$），下界是最小特征值（${\lambda }_n$）。
证明：
令 $\mathbf{\Lambda }=diag({\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_n)$，这些特征值对应的归一化特征矢量为 { u 1 , u 2 , ⋯   , u n } { mathbf u_1,mathbf u_2,cdots,mathbf u_n} {u1​,u2​,⋯,un​}，即 $\Vert {\mathbf{u}}_i\Vert =1$，且${\mathbf{u}}_i^T{\mathbf{u}}_j=0\text{ (if i not equal j)}$。令$\mathbf{U}=[{\mathbf{u}}_1,{\mathbf{u}}_2,\cdots ,{\mathbf{u}}_n]$，则有 $\mathbf{A}=\mathbf{U}\mathbf{\Lambda }{\mathbf{U}}^{\ast }$。代入（2）有：
$$\begin{gathered} R=\frac{{\mathbf{x}}^{\ast }\mathbf{A}\mathbf{x}}{{\mathbf{x}}^{\ast }\mathbf{x}}=\frac{{\mathbf{x}}^{\ast }\mathbf{U}\mathbf{\Lambda }{\mathbf{U}}^{\ast }\mathbf{x}}{{\mathbf{x}}^{\ast }\mathbf{I}\mathbf{x}}=\frac{{\mathbf{x}}^{\ast }\mathbf{U}\mathbf{\Lambda }{\mathbf{U}}^{\ast }\mathbf{x}}{{\mathbf{x}}^{\ast }\mathbf{U}{\mathbf{U}}^{\ast }\mathbf{x}} \\ \text{Let }\mathbf{z}={\mathbf{U}}^{\ast }\mathbf{x}=[z_i],i\in [1,n] \\ R=\frac{{\mathbf{z}}^{\ast }\mathbf{\Lambda }\mathbf{z}}{{\mathbf{z}}^{\ast }\mathbf{z}}=\frac{{\lambda }_1|z_1{|}^2+\cdots +{\lambda }_n|z_n{|}^2}{|z_1{|}^2+\cdots +|z_n{|}^2}\le {\lambda }_1(4) \end{gathered}$$
同理，可得：
$$R=\frac{{\mathbf{x}}^{\ast }\mathbf{A}\mathbf{x}}{{\mathbf{x}}^{\ast }\mathbf{x}}\ge \frac{{\lambda }_n(|z_1{|}^2+\cdots +|z_n{|}^2)}{|z_1{|}^2+\cdots +|z_n{|}^2}={\lambda }_n(5)$$
证毕。

可利用（4）最大化原则、（5）最小化原则求出H矩阵的最大和最小特征值，能否求出其余的特征值（eigenvalues）：${\lambda }_2,\cdots ,{\lambda }_{n-1}$？倘若仅考虑与最大特征值的特征矢量 ${\mathbf{u}}_1$ 的正交子空间中的向量 $\mathbf{x}$，即 ${\mathbf{x}}^T{\mathbf{u}}_1=0$，令：
$$\mathbf{z}={\mathbf{U}}^{\ast }\mathbf{x}=[{\mathbf{u}}_1,\cdots ,{\mathbf{u}}_n{]}^{\ast }\mathbf{x}=(0,z_2,z_3,\cdots ,z_n{)}^T$$
根据上述 Hermitian矩阵 的性质3，可以令 $\mathbf{U}$ 是$\mathbf{A}$列矢量（col vector）所在矢量空间（vector space）的标准正交基，$\mathbf{z}$ 是任意非0矢量$\mathbf{x}$ 在此基上的坐标矢量。因此有：
$$\begin{gathered} \frac{{\mathbf{x}}^{\ast }\mathbf{A}\mathbf{x}}{{\mathbf{x}}^{\ast }\mathbf{x}}=\frac{{\mathbf{x}}^{\ast }\mathbf{U}\mathbf{\Lambda }{\mathbf{U}}^{\ast }\mathbf{x}}{{\mathbf{x}}^{\ast }\mathbf{x}}=\frac{{\mathbf{z}}^{\ast }\mathbf{\Lambda }\mathbf{z}}{{\mathbf{z}}^{\ast }\mathbf{z}}=\frac{{\lambda }_2|z_2{|}^2+\cdots +{\lambda }_n|z_n{|}^2}{|z_2{|}^2+\cdots +|z_n{|}^2}\le {\lambda }_2(6) \\ . \\ \text{as }{\mathbf{z}}^{\ast }\mathbf{z}={\mathbf{x}}^{\ast }\mathbf{x} \end{gathered}$$
也就有:
$$\underset{\mathbf{x}̸=0,\mathbf{x}\perp {\mathbf{u}}_1}{\max }\frac{{\mathbf{x}}^{\ast }\mathbf{A}\mathbf{x}}{{\mathbf{x}}^{\ast }\mathbf{x}}={\lambda }_2(7)$$
(7)求解必须要知道 ${\mathbf{u}}_1$，若要绕过它，考虑 ${\mathbb{C}}^n$ 中任意向量 $\mathbf{w}$，令 $\mathbf{x}\perp \mathbf{w}$ ，则有：
$$\begin{gathered} \text{Let }\mathbf{z}={\mathbf{U}}^{\ast }\mathbf{x}\text{ , so} \\ 0={\mathbf{x}}^{\ast }\mathbf{w}=(\mathbf{U}\mathbf{z}{)}^{\ast }\mathbf{w}={\mathbf{z}}^{\ast }{\mathbf{U}}^{\ast }\mathbf{w},\text{ so} \\ \mathbf{z}\perp {\mathbf{U}}^{\ast }\mathbf{w} \end{gathered}$$
令 V = { z ∈ C n ∣ z ⊥ U ∗ w } V={zin mathbb C^nvert mathbf zbot mathbf U^*mathbf w} V={z∈Cn∣z⊥U∗w}，且 V ′ = { z ∈ C n ∣ z ⊥ U ∗ w , z 3 = ⋯ = z n = 0 } V'={zin mathbb C^nvert mathbf zbot mathbf U^*mathbf w,z_3=cdots=z_n=0} V′={z∈Cn∣z⊥U∗w,z3​=⋯=zn​=0}，则有 $V^{\prime }\subset V$，所以：
$$\begin{gathered} \underset{\mathbf{x}̸=0,\mathbf{x}\perp \mathbf{w}}{\max }\frac{{\mathbf{x}}^{\ast }\mathbf{A}\mathbf{x}}{{\mathbf{x}}^{\ast }\mathbf{x}}=\underset{\mathbf{z}̸=0,\mathbf{z}\perp {\mathbf{U}}^{\ast }\mathbf{w}}{\max }\frac{{\mathbf{z}}^{\ast }\mathbf{\Lambda }\mathbf{z}}{{\mathbf{z}}^{\ast }\mathbf{z}}=\underset{\mathbf{z}̸=0,\mathbf{z}\in V}{\max }\frac{{\mathbf{z}}^{\ast }\mathbf{\Lambda }\mathbf{z}}{{\mathbf{z}}^{\ast }\mathbf{z}} \\ \ge \underset{\mathbf{z}̸=0,\mathbf{z}\in V^{\prime }}{\max }\frac{{\mathbf{z}}^{\ast }\mathbf{\Lambda }\mathbf{z}}{{\mathbf{z}}^{\ast }\mathbf{z}}=\underset{\mathbf{z}̸=0,\mathbf{z}\in V^{\prime }}{\max }\frac{{\lambda }_1|z_1{|}^2+{\lambda }_2|z_2{|}^2}{|z_1{|}^2+|z_2{|}^2}\ge {\lambda }_2(8) \end{gathered}$$
前面的不等式成立的原因是在 V ′ ∖ { 0 } V'setminus{0} V′∖{0} 所得的最大值，它必不大于在 V ∖ { 0 } Vsetminus{0} V∖{0} 中的最大值；后面的不等式则源于 ${\lambda }_1\ge {\lambda }_2$。因为 $\mathbf{w}$ 是任意固定向量，对于所有可能的 $\mathbf{w}$ 获得的极小值也必然大于 ${\lambda }_2$，亦即：
$$\underset{\mathbf{w}}{\min }\underset{\mathbf{x}̸=0,\mathbf{x}\perp \mathbf{w}}{\max }\frac{{\mathbf{x}}^{\ast }\mathbf{A}\mathbf{x}}{{\mathbf{x}}^{\ast }\mathbf{x}}\ge {\lambda }_2(9)$$
此不等式的等号成立于$\mathbf{w}={\mathbf{u}}_1$，因此有：
$$\underset{\mathbf{w}}{\min }\underset{\mathbf{x}̸=0,\mathbf{x}\perp \mathbf{w}}{\max }\frac{{\mathbf{x}}^{\ast }\mathbf{A}\mathbf{x}}{{\mathbf{x}}^{\ast }\mathbf{x}}={\lambda }_2(10)$$
设想在任意的n-1维子空间，亦即与$\mathbf{w}$ 正交的正交子空间中寻找Rayleigh商的最大值，这个子空间未必包含任何特征向量，但我们可以确知其中必定有某个子空间不包含对应最大特征值${\lambda }_1$的特征向量${\mathbf{u}}_1$，而从该子空间所能找到的最大Rayleigh商正好是在所有n-1维空间所能找到的最小值！
如果交换max和min位置，我们可以得到：
$$\underset{\mathbf{w}}{\max }\underset{\mathbf{x}̸=0,\mathbf{x}\perp \mathbf{w}}{\min }\frac{{\mathbf{x}}^{\ast }\mathbf{A}\mathbf{x}}{{\mathbf{x}}^{\ast }\mathbf{x}}={\lambda }_{n-1}(11)$$
完整的最小-最大定理还包括其他的特征值的推导。详细见【1】：
https://ccjou.wordpress.com/2010/03/16/hermitian-矩陣特徵值的變化界定/
本文上半部分几乎都是抄自于此。

二、谱图分析（Spectral Graph Analysis）

详细可参看：

• 谱图（Spectral Graph Theory）理解（1）
  https://blog.csdn.net/StreamRock/article/details/82754539
• 谱图（Spectral Graph Theory）理解（2）
  https://blog.csdn.net/StreamRock/article/details/82769865
  “谱图”简单说就是通过矩阵的方式，描述图中顶点（Vertex）与边（Edge，顶点之间的连线）的关系，这些关系可以归结以下矩阵关系为：
  L —— 图（Graph）的Laplacian矩阵，形状为$n\times n$，n是Graph的顶点数量；
  W ——图（Graph）的Weight矩阵，反映边的特性，是实对称阵(Real Symmatry Matrix);
  D ——图（Graph）的Degree矩阵，反映顶点的特性，是对角矩阵（Diagonal Matrix），其中对角元素 $d_{ii}={\sum }_j{w}_{ij}$
  有：
  $$L=D-W(12)$$
  $L$ 是一个实对称矩阵，若Graph为全连通图，则$L$ 满秩，其列空间的基为n维，将其特征值按从大到小排列有：
  ${\lambda }_1\ge {\lambda }_2\cdots \ge {\lambda }_n$，则定义$\mathbf{\Lambda }=diag({\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_n)$
  其对应的特征矢量，可进行标准化（正交和归一化处理）有：
  ${\mathbf{u}}_1\perp {\mathbf{u}}_2\cdots \perp {\mathbf{u}}_n,\text{ where }\Vert {\mathbf{u}}_i\Vert =1$，可定义$\mathbf{U}=[{\mathbf{u}}_1,{\mathbf{u}}_2,\cdots ,{\mathbf{u}}_n]$
  $L$ 符合上述Courant-Fischer定理的要求，因此可以用该定理讨论Graph的Laplacian矩阵。

三、图的分割

详细内容可参看《Normalized Cuts and Image Segmentation》【2】，或：谱图（Spectral Graph Theory）理解（2）【3】
https://blog.csdn.net/StreamRock/article/details/82769865
图的分割是指将图分割成几部分，其中最简单的是二分割（two-way partition）：令 $G=(V,E)$，V是图G的所有顶点组成的顶点集，E是顶点间的连线。A是V的一个子集，则有：$A+\bar{A}=V$，因而$A,\bar{A}$是V的一个二分割。将Graph表示成矩阵形式，则可以获得该Graph的Laplacian矩阵。通过对Laplacian特征值的讨论，分割问题最后可以归结为：
{ min ⁡ x N c u t ( x ) = min ⁡ y y T ( D − W ) y y T D y   where  y ( i ) ∈ { 1 , − b }  and  y T D 1 = 0 ( 13 ) left{ begin{array}{c} min_xNcut(mathbf x)=min_yfrac{mathbf y^T(D-W)mathbf y}{mathbf y^TDmathbf y}\ \ text{where } y(i)in {1,-b}text{ and }mathbf y^TDmathbf 1=mathbf 0end{array} right.qquad(13) ⎩⎪⎨⎪⎧​minx​Ncut(x)=miny​yTDyyT(D−W)y​ where y(i)∈{1,−b} and yTD1=0​(13)
详细的推导可见【2】、【3】。将y(i)的取值范围放宽到整个实数域，观察到（13）min()中分母部分 $y^{T}Dy$ 与Rayleigh商稍有差别，因此做变量转换，令 $\mathbf{z}={\mathbf{D}}^{\frac{1}{2}}\mathbf{y}$，代入（13）为：
$$\begin{gathered} \underset{x}{\min }Ncut(\mathbf{x})=\underset{y}{\min }\frac{{\mathbf{y}}^T(D-W)\mathbf{y}}{{\mathbf{y}}^{T}D\mathbf{y}}=\underset{y}{\min }\frac{{\mathbf{z}}^T{D}^{\frac{1}{2}}(D-W)D^{\frac{1}{2}}\mathbf{z}}{{\mathbf{z}}^T\mathbf{z}} \\ \text{Let }\mathcal{L}=D^{-\frac{1}{2}}(D-W)D^{-\frac{1}{2}},\text{ so } \\ \underset{x}{\min }Ncut(\mathbf{x})=\underset{z}{\min }\frac{{\mathbf{z}}^T\mathcal{L}\mathbf{z}}{{\mathbf{z}}^T\mathbf{z}},\text{and }{\mathbf{y}}^{T}D1=0(14) \end{gathered}$$
这是典型的Rayleigh商求最小值，由Courant-Fischer定理可知（14）最小值是在其最小特征值-特征矢量处得到，于是（14）等价于求解 $\mathcal{L}$ 的特征值-特征矢量，于是有：
$$\begin{gathered} \mathcal{L}\mathbf{z}=\lambda \mathbf{z} \\ {D}^{-\frac{1}{2}}(D-W)D^{-\frac{1}{2}}\mathbf{z}=\lambda \mathbf{z}(15) \end{gathered}$$
因为$(D-W)1=0$，因此 ${\mathbf{z}}_n=D^{\frac{1}{2}}1$ 是 $\mathcal{L}$ 的特征值为0（最小特征值）的特征矢量。联系到(13)的约束条件：
$${\mathbf{y}}^{T}D1=0\Rightarrow {\mathbf{y}}^T{D}^{\frac{1}{2}}{D}^{\frac{1}{2}}1=0\Rightarrow {\mathbf{z}}^T\cdot {\mathbf{z}}_n=0(16)$$
（16）表示$\mathbf{z}$ 的取值空间必垂直于最小特征向量，由（9）、（10）有（14）的最小值等于$\mathcal{L}$第二最小特征值${\lambda }_{n-1}$，此时$\mathbf{z}$等于特征向量${\mathbf{u}}_{n-1}$。于是，图的分割问题最终转化成在寻找Graph的Laplacian矩阵第二小的特征值和特征向量问题。

四、图像（Image）前景与背景的分割

一幅图像（Image）可以看成是一个图（Graph），图像中每一个像素（pixel）对应图中每一个顶点（vertex），可根据像素之间的关系可定义边。于是一幅图像可以用图的Laplacian矩阵表示，对于一幅图进行前景和背景分割，可看作是图的二分割。
一幅$n\times n$图像，对应的Laplacian矩阵为$n^2\times n^2$，以下讨论仅通过亮度通道进行分割的情况：
1、定义权重矩阵W(有时又称为亲和度矩阵A，Affinity Matrix，亲和矩阵如何定义，往往是不同图像分割算法区别的关键地方）。为简便起见，定义它的每个元素如下：
$$w_{ij}=\{\begin{array}{cc}{e}^{-\frac{\Vert X_i-X_j{\Vert }_2^2}{{\sigma }_x^2}}& \text{if ∥X(i)−X(j)∥2<r,and i̸=j}\\ 0& \text{otherwise}\end{array}(17)$$
(17)中，$X_i$ 表示像素上的亮度，$X(i)$ 表示像素的位置，$\Vert X(i)-X(j){\Vert }_2<r$ 表示两个像素之间的几何距离小于r，${\sigma }_x^2$是像素亮度的方差。
W是实对称矩阵，再由W定义对角矩阵D，我们便可以得到图像的Laplacian矩阵$L=D-W$。由（16）可知，图像分割问题可转化为寻找它的Laplacian矩阵第二小特征矢量问题，即：
$${\mathbf{z}}_{n-1}=\arg \underset{\mathbf{z}\perp D^{\frac{1}{2}}1}{\min }\frac{{\mathbf{z}}^T{D}^{-\frac{1}{2}}(D-W)D^{-\frac{1}{2}}\mathbf{z}}{{\mathbf{z}}^T\mathbf{z}}(18)$$
由于我们在定义亲和度矩阵时，采用了window方式，因此$\mathcal{L}$必然是非常稀疏的矩阵，可以通过Lanczos algorithm方法进行求解，详细叙述在：
https://en.wikipedia.org/wiki/Lanczos_algorithm

小结：

少辉常说，学习应当放在某个情景中，则所学知其所为，效率会大大提高。通过图像分割来学习这其中的图谱理论、Courant-Fischer定理、Lanczos algorithm应当属于此类情景学习了。

参考资料：
【1】https://ccjou.wordpress.com/2010/03/16/hermitian-矩陣特徵值的變化界定/
【2】《Normalized Cuts and Image Segmentation》
【3】谱图（Spectral Graph Theory）理解（2）
https://blog.csdn.net/StreamRock/article/details/82769865

最后

以上就是个性面包为你收集整理的Courant-Fischer定理、谱图分析和图的分割的全部内容，希望文章能够帮你解决Courant-Fischer定理、谱图分析和图的分割所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。