Rayleigh Quotient and Generalized Rayleigh Quotient.
- 瑞利商的定义
- 瑞利商的性质
- 广义瑞利商
- 瑞利商在机器学习中的应用
1. 瑞利商的定义
对于一个Hermitan矩阵$A$(复域的共轭对称矩阵,满足$A^H=A$)及非零向量$\textbf{x}=(x_1,…,x_n)^T$，瑞利商(Rayleigh Quotient)定义为：
\[R(A,x) = \frac{x^HAx}{x^Hx}\]其中$x^H$是$x$的共轭转置向量。在实数域中瑞利商可以表示为：
\[R(A,x) = \frac{x^TAx}{x^Tx}\]2. 瑞利商的性质
设矩阵$A$的特征值与特征向量分别为$\lambda_1,…,\lambda_n,v_1,…,v_n$，且满足：
\[\lambda_{min}=\lambda_1≤\lambda_2≤...≤\lambda_n=\lambda_{max}\]则瑞利商的取值范围是：
\[\lambda_{min}≤\frac{x^HAx}{x^Hx}≤\lambda_{max}\]⚪ 证明方法 1
由于$A$是Hermitan矩阵，则存在酉矩阵$U$(复正交矩阵)对$A$进行相似对角化：
\[A = U \Lambda U^H\]其中对角矩阵$\Lambda=diag(\lambda_1,\lambda_2,…,\lambda_n)$。将上式代入瑞利商：
\[R(A,x) = \frac{x^HAx}{x^Hx} = \frac{x^HU \Lambda U^Hx}{x^Hx} = \frac{(U^Hx)^H \Lambda (U^Hx)}{x^Hx}\]记向量$p=U^Hx=(p_1,…,p_n)^T$，则：
\[R(A,x) = \frac{p^H \Lambda p}{x^Hx} = \frac{\sum_{i=1}^{n} \lambda_i |p_i|^2}{\sum_{i=1}^{n}|x_i|^2}\]根据特征值的大小关系，可得不等式：
\[\lambda_1 \sum_{i=1}^{n} |p_i|^2≤\sum_{i=1}^{n} \lambda_i |p_i|^2≤\lambda_n \sum_{i=1}^{n} |p_i|^2\]因此可得：
\[\frac{\lambda_1 \sum_{i=1}^{n} |p_i|^2}{\sum_{i=1}^{n}|x_i|^2}≤R(A,x)≤\frac{\lambda_n \sum_{i=1}^{n} |p_i|^2}{\sum_{i=1}^{n}|x_i|^2}\]记$u_{ij}$为酉矩阵$U$的第$i$行第$j$列元素，则：
\[p_i=\sum_{j=1}^{n}{u^H}_{ij}x_j=\sum_{j=1}^{n}u_{ji}x_j, \quad p_i^T=\sum_{j=1}^{n}x_ju_{ij}\] \[|p_i|^2 = p_i^Tp_i = \sum_{j=1}^{n}x_ju_{ij}\sum_{k=1}^{n}u_{ki}x_k = \sum_{j=1}^{n}\sum_{k=1}^{n}x_ju_{ij}u_{ki}x_k\]进一步有：
\[\sum_{i=1}^{n} |p_i|^2 = \sum_{i=1}^{n} \sum_{j=1}^{n}\sum_{k=1}^{n}x_ju_{ij}u_{ki}x_k = \sum_{j=1}^{n}\sum_{k=1}^{n}x_jx_k (\sum_{i=1}^{n}u_{ij}u_{ki})\]由于$U$是酉矩阵，因此$U^HU=I$，写作$I_{jk}=\sum_{i=1}^{n}u_{ji}u_{ik}$。当$j≠k$时$I_{jk}=0$，当$j=k$时$I_{jk}=1$。因此上式进一步化简为：
\[\sum_{i=1}^{n} |p_i|^2 = \sum_{j=k}^{} x_jx_k = \sum_{i=1}^{n} |x_i|^2\]代入原不等式，得：
\[\lambda_1≤R(A,x)≤\lambda_n\]⚪ 证明方法 2
注意到对于任意非零实数$c$，使用$x’=cx$取代$x$，计算瑞利商：
\[R(A,x') = \frac{x'^TAx'}{x'^Tx'} = \frac{cx^TAcx}{cx^Tcx} = \frac{x^TAx}{x^Tx} = R(A,x)\]因此对向量$x$等比例缩放不影响瑞利商的值。不妨取$x^Tx=1$，此时对瑞利商求极值，就是在约束$x^Tx=1$下，求$R(A,x) = x^TAx$的极值。
采用拉格朗日乘子法，定义拉格朗日函数：
\[L(x,\alpha)= x^TAx-\alpha(x^Tx-1)\]上式对$x$求梯度：
\[\frac{\partial L(x,\alpha)}{\partial x} = 2Ax-2\alpha x\]令梯度为$0$，对应极小值或极大值的情况，此时有：
\[Ax=\alpha x\]即$A$的特征值$\alpha$使得瑞利商取得极值，且极值为$R(A,x) = x^TAx =\alpha x^Tx = \alpha$。
3. 广义瑞利商
对于一个Hermitan矩阵$A$,$B$及非零向量$x=(x_1,…,x_n)^T$，其中$B$是正定矩阵，则其广义瑞利商(Generalized Rayleigh Quotient)定义为：
\[R(A,B,x) = \frac{x^HAx}{x^HBx}\]⚪ 化简方法 1
记$x = B^{-\frac{1}{2}}x’$，则上式表示为：
\[R(A,B,x) = \frac{x^HAx}{x^HBx} = \frac{(B^{-\frac{1}{2}}x')^HAB^{-\frac{1}{2}}x'}{(B^{-\frac{1}{2}}x')^HBB^{-\frac{1}{2}}x'} \\ = \frac{ {x'}^H {B^{-\frac{1}{2}}} AB^{-\frac{1}{2}}x' }{ {x'}^H {B^{-\frac{1}{2}}} BB^{-\frac{1}{2}}x' } = \frac{ {x'}^H B^{-\frac{1}{2}} AB^{-\frac{1}{2}}x' }{ {x'}^Hx' } = R(B^{-\frac{1}{2}} AB^{-\frac{1}{2}},x')\]因此$R(A,B,x)$的最大值和最小值分别为矩阵$B^{-\frac{1}{2}} AB^{-\frac{1}{2}}$的最大特征值和最小特征值。由于矩阵$B^{-\frac{1}{2}} AB^{-\frac{1}{2}}$与矩阵$B^{-1} A$具有相同的特征值，因此$R(A,B,x)$的最大值和最小值分别为矩阵$B^{-1} A$的最大特征值和最小特征值。
⚪ 化简方法 2
由于对向量$x$等比例缩放不影响广义瑞利商的值，不妨取$x^TBx=1$，此时对广义瑞利商求极值，就是在约束$x^TBx=1$下，求$R(A,B,x) = x^TAx$的极值。
采用拉格朗日乘子法，定义拉格朗日函数：
\[L(x,\alpha)= x^TAx-\alpha(x^TBx-1)\]上式对$x$求梯度：
\[\frac{\partial L(x,\alpha)}{\partial x} = 2Ax-2\alpha Bx\]令梯度为$0$，对应极小值或极大值的情况，此时有：
\[B^{-1}Ax=\alpha x\]即$B^{-1}A$的特征值$\alpha$使得广义瑞利商取得极值，且极值为$R(A,B,x) = x^TB^{-1}Ax =\alpha x^Tx = \alpha$。
4. 瑞利商在机器学习中的应用
一些目标函数为(广义)瑞利商的机器学习算法介绍如下：
⚪ 计算谱范数
参数矩阵的谱范数(spectral norm)定义为：
\[||W||_2 = \mathop{\max}_{x \neq 0} \frac{||Wx||}{||x||}\]谱范数是一种由向量范数诱导出来的矩阵范数，作用相当于向量的模长。注意到谱范数$||W||_2$的平方为：
\[||W||_2^2 = \mathop{\max}_{x \neq 0} \frac{x^TW^TWx}{x^Tx}\]上式右端为瑞利商，因此谱范数$||W||_2$的平方的取值为$W^TW$的最大特征值。
⚪ 线性判别分析
线性判别分析是指把样本集$x$进行线性投影$w^Tx$，从而让相同类别样本的类内方差足够小（用类内散度矩阵$S_w = \Sigma_0+\Sigma_1$建模）、不同类别样本的类间距离足够大（用类间散度矩阵$S_b = (\mu_0-\mu_1)(\mu_0-\mu_1)^T$建模）；目标函数可写作：
\[J = \frac{w^TS_bw}{w^TS_ww}\]上式为广义瑞利商，因此投影向量$w$为矩阵$S_w^{-1}S_b$最大特征值对应的特征向量。
⚪ 主成分分析
PCA的目标函数为最小化重构损失，可以等价地表示为如下约束优化问题：
\[\begin{aligned} \mathop{\max}_{u} \quad & \frac{1}{N} \sum_{n=1}^{N} {u^T(x_n - \overline{x})(x_n - \overline{x})^Tu} \\ s.t. \quad & u^Tu = 1 \end{aligned}\]上式为瑞利商，因此投影方向$u$可以由样本归一化后的协方差矩阵$(X-\overline{X})^T(X+\overline{X})$最大的$k$个特征值对应的特征向量构造。
⚪ 局部线性嵌入 LLE
在已知高维空间中任意样本点$x$如何被邻域中其他样本点线性组合后（即求出权重$W$后），可以利用重构损失最小原则在低维空间中构建降维表示$Z$的目标函数：
\[\begin{aligned} \mathop{\min}_{Z} \quad & \text{tr}(Z^T(I_{N\times N}-W)^T(I_{N\times N}-W)Z) \\ s.t. \quad & Z_i^TZ_i = I_{d'\times d'} \end{aligned}\]上式为瑞利商，因此降维表示$Z$可以由矩阵$(I_{N\times N}-W)^T(I_{N\times N}-W)$最小的$k$个特征值对应的特征向量构造。
⚪ 谱聚类
谱聚类通过对所有数据点组成的图进行切图，让切图后不同的子图间边权重之和尽可能低，而子图内的边权重之和尽可能高，从而达到聚类的目的。
在RatioCut中，对每个切图，不光考虑最小化$cut(A_1,…,A_K)$，还同时考虑最大化每个子图点的个数，即：
\[RatioCut(A_1,...,A_K) = \frac{1}{2}\sum_{k=1}^K \frac{W(A_k,\overline{A}_k)}{|A_k|}\]最小化RatioCut等价于最小化$H^TLH$，其中$L$是图拉普拉斯矩阵，$H$是待求解的指示矩阵，且满足$H^TH=I$。
