瑞丽熵 (Rayleigh quotient) 两种启发式证明

瑞丽熵定义如下：

R ( A , x ) = x ∗ A x x ∗ x R(A, x)=\frac{x^{*} A x}{x^{*} x} R(A,x)=x∗xx∗Ax​ 其中矩阵 A A A为 n × n n \times n n×n的对称矩阵（Hermitian)。

有： max ⁡ x ≠ 0 x H A x x H x = max ⁡ x H x = 1 x H A x x H x = λ m a x min ⁡ x ≠ 0 x H A x x H x = min ⁡ x H x = 1 x H A x x H x = λ m i n \begin{aligned} &\max _{\boldsymbol{x} \neq 0} \frac{\boldsymbol{x}^{\mathrm{H}} \boldsymbol{A} \boldsymbol{x}}{\boldsymbol{x}^{\mathrm{H}} \boldsymbol{x}}=\max _{\boldsymbol{x}^{\mathrm{H}} \boldsymbol{x}=1} \frac{\boldsymbol{x}^{\mathrm{H}} \boldsymbol{A} \boldsymbol{x}}{\boldsymbol{x}^{\mathrm{H}} \boldsymbol{x}}=\boldsymbol{\lambda}_{\mathrm{max}}\\ &\min _{\boldsymbol{x} \neq 0} \frac{\boldsymbol{x}^{\mathrm{H}} \boldsymbol{A} \boldsymbol{x}}{\boldsymbol{x}^{\mathrm{H}} \boldsymbol{x}}=\min _{\boldsymbol{x}^{\mathrm{H}} \boldsymbol{x}=1} \frac{\boldsymbol{x}^{\mathrm{H}} \boldsymbol{A} \boldsymbol{x}}{\boldsymbol{x}^{\mathrm{H}} \boldsymbol{x}}=\lambda_{\mathrm{min}} \end{aligned} ​x​=0max​xHxxHAx​=xHx=1max​xHxxHAx​=λmax​x​=0min​xHxxHAx​=xHx=1min​xHxxHAx​=λmin​​

证明1：

因为 A A A为对称矩阵，可特征分解为 A = V T Σ V A= V^T\Sigma V A=VTΣV。 V = [ v 1 , . . . , v n ] V = [v_1,..., v_n] V=[v1​,...,vn​], Σ = d i a g ( λ 1 , . . . , λ n ) \Sigma=\mathrm{diag}(\lambda_1,...,\lambda_n) Σ=diag(λ1​,...,λn​)。不妨设 λ 1 ≥ λ 2 ≥ . . . ≥ λ n \lambda1 \ge \lambda_2 \ge ...\ge \lambda_n λ1≥λ2​≥...≥λn​。

对原式进行如下展开。可得

R ( A , x ) = x ∗ A x x ∗ x = ∑ i = 1 n λ i y i 2 ∑ i = 1 n y i 2 R(A, x)=\frac{x^{*} A x}{x^{*} x}=\frac{\sum_{i=1}^{n} \lambda_{i} y_{i}^{2}}{\sum_{i=1}^{n} y_{i}^{2}} R(A,x)=x∗xx∗Ax​=∑i=1n​yi2​∑i=1n​λi​yi2​​

显然有： λ 1 = ∑ i = 1 n λ 1 y i 2 ∑ i = 1 n y i 2 ≤ ∑ i = 1 n λ i y i 2 ∑ i = 1 n y i 2 ≤ ∑ i = 1 n λ n y i 2 ∑ i = 1 n y i 2 = λ n \lambda_1 = \frac{\sum_{i=1}^{n} \lambda_{1} y_{i}^{2}}{\sum_{i=1}^{n} y_{i}^{2}}\le\frac{\sum_{i=1}^{n} \lambda_{i} y_{i}^{2}}{\sum_{i=1}^{n} y_{i}^{2}}\le\frac{\sum_{i=1}^{n} \lambda_{n} y_{i}^{2}}{\sum_{i=1}^{n} y_{i}^{2}}=\lambda_n λ1​=∑i=1n​yi2​∑i=1n​λ1​yi2​​≤∑i=1n​yi2​∑i=1n​λi​yi2​​≤∑i=1n​yi2​∑i=1n​λn​yi2​​=λn​

得证。 同时： 当且仅当 y 1 = 0 , . . . y n − 1 = 0 y_1=0,...y_{n-1}=0 y1​=0,...yn−1​=0成立时，等号成立，取到最大值。 因此，当 x x x为 A A A的最大特征向量时，瑞丽商最大，为最大特征值。

证明2：

易见，我们可以引入一个限制条件而不影响瑞丽商的结果： x T x = 1 x^Tx=1 xTx=1

将这个限制条件用拉格朗日乘子法加入目标函数，有：

L = R ( A , x ) + λ ( x T x − 1 ) = x T A x + λ ( x T x − 1 ) L = R(A, x) + \lambda (x^{T}x-1) = x^{T} A x+ \lambda (x^{T}x-1) L=R(A,x)+λ(xTx−1)=xTAx+λ(xTx−1).

对 x x x求导，有 A x + λ x = 0 Ax+\lambda x=0 Ax+λx=0时取到极值。 那么显然， x x x为 A A A的特征向量（特征分解的定义）。注意这里的 λ \lambda λ是拉格朗日乘子，而不是特征值。

由此，可知 x x x为 A A A的特征向量后， x T A x x^{T} A x xTAx的结果就是对应的特征值。 证毕。

拓展

X \mathrm{X} X为矩阵时 求解R的最值： R ( A , X ） = t r ( X T A X ( X T X ) − 1 ) R(A, \mathrm{X}）=\mathrm{tr}({\mathrm{X}^{T} A \mathrm{X}}({\mathrm{X}^{T} \mathrm{X}})^{-1}) R(A,X）=tr(XTAX(XTX)−1)

令 X = U Σ V T \mathbf{X}=U\Sigma V^T X=UΣVT为特征值分解。

R = tr ⁡ ( V ∑ T U A U T ∑ V T ( V Σ T Σ V T ) − 1 ) = tr ⁡ ( ∑ T U A U T Σ ( Σ T Σ ) − 1 ) = tr ⁡ ( U A U T [ I 0 ] [ I 0 ] ) = tr ⁡ ( Q T A Q ) Q = U T [ I 0 ] \begin{aligned} &R=\operatorname{tr}\left(\mathrm{V} \sum^{T} U A U^{T} \sum V^{T}\left(V \Sigma^{T} \Sigma V^{T}\right)^{-1}\right)\\ &=\operatorname{tr}\left(\sum^{T} U A U^{T} \Sigma\left(\Sigma^{T} \Sigma\right)^{-1}\right)\\ &=\operatorname{tr}\left(U A U^{T}\left[\begin{array}{l} {I} \\ {0} \end{array}\right]\left[\begin{array}{ll} {I} & {0} \end{array}\right]\right)\\ &=\operatorname{tr}\left(Q^{T} A Q\right)\\ &Q=U^{T}\left[\begin{array}{l} {I} \\ {0} \end{array}\right] \end{aligned} ​R=tr(V∑T​UAUT∑VT(VΣTΣVT)−1)=tr(∑T​UAUTΣ(ΣTΣ)−1)=tr(UAUT[I0​][I​0​])=tr(QTAQ)Q=UT[I0​]​

这说明，我们可以直接优化最后的式子 tr ⁡ ( Q T A Q ) \operatorname{tr}\left(Q^{T} A Q\right) tr(QTAQ)。显然 Q T Q = I Q^TQ=I QTQ=I。因此，对比R的原始式子，我们可以从一开始就增加限制条件， X T X = I X^TX=I XTX=I。

而对于 max ⁡ X    t r ( X T A X )  s.t.  X T X = I \begin{aligned} \max_{X} &\;\mathrm{tr}(X^TAX)\\ \text { s.t. } & X^TX=I \end{aligned} Xmax​ s.t. ​tr(XTAX)XTX=I​ 有一个巧妙的启发式证明 max ⁡ t r ( X T A X ) = ∑ λ i \max \mathrm{tr}(X^TAX) = \sum \lambda_i maxtr(XTAX)=∑λi​, 其中 λ i \lambda_i λi​ 代表 A A A 的第 i i i 大特征向量。 首先， 当 X X X 的每列分别为 A A A最大的几个特征向量时， t r ( X T A X ) = ∑ λ i \mathrm{tr}(X^TAX) = \sum \lambda_i tr(XTAX)=∑λi​。 因此 max ⁡ t r ( X T A X ) ≥ ∑ λ i \max \mathrm{tr}(X^TAX)\ge \sum \lambda_i maxtr(XTAX)≥∑λi​。 然后根据定理： t r ( X T A X ) ≤ A = ∑ λ i \mathrm{tr}(X^TAX)\le \mathrm{A}=\sum\lambda_i tr(XTAX)≤A=∑λi​ 得到上界。 结合可知： max ⁡ t r ( X T A X ) = ∑ λ i \max \mathrm{tr}(X^TAX) = \sum \lambda_i maxtr(XTAX)=∑λi​

定理是如何证明的呢？ t r ( X T A X ) = t r ( X X T A ) = t r ( ( I N s 0 ) K T A K ) ≤ t r ( K T A K ) = t r ( A ) \mathrm{tr}(X^TAX)=\mathrm{tr}(XX^TA)=\mathrm{tr}(\left(\begin{array}{cc} \mathbf{I}_{N_{s}} & \\ & 0 \end{array}\right){K}^{T} A {K})\le \mathrm{tr}(K^TAK)=\mathrm{tr}(A) tr(XTAX)=tr(XXTA)=tr((INs​​​0​)KTAK)≤tr(KTAK)=tr(A)

其中利用了 X X T = K ( I N s 0 ) K T XX^T=K\left(\begin{array}{cc} \mathbf{I}_{N_{s}} & \\ & 0 \end{array}\right){K}^{T} XXT=K(INs​​​0​)KT的EVD分解。 (因为 X X T = I XX^T=I XXT=I)。