瑞利商性质及证明（上下界）

目录

前言瑞利商定义瑞利商性质瑞利商性质证明瑞利商的上下界瑞利商的上下确界

参考

前言

在推导标准化拉普拉斯矩阵的特征值范围时，用到了瑞利商，它也是LDA最大化目标函数使用的定义。

瑞利商定义

瑞利商的定义为：

R

(

A

,

x

)

=

x

T

A

x

x

T

x

R(A,x)=\frac{x^TAx}{x^Tx}

R(A,x)=xTxxTAx​，其中

A

A

A 为

n

×

n

n\times n

n×n 对称矩阵，

x

x

x 为

n

n

n 维度向量。

瑞利商性质

设对称矩阵

A

A

A 的特征值为

λ

1

≤

λ

2

≤

⋯

≤

λ

n

\lambda_1\le\lambda_2\le\cdots\le\lambda_n

λ1​≤λ2​≤⋯≤λn​，对应的特征向量为

v

1

,

v

2

,

⋯

,

v

n

v_1,v_2,\cdots,v_n

v1​,v2​,⋯,vn​。有：

m

a

x

x

R

(

A

,

x

)

=

λ

n

m

i

n

x

R

(

A

,

x

)

=

λ

1

\mathop{max}\limits_{x}R(A,x)=\lambda_n \\ \mathop{min}\limits_{x}R(A,x)=\lambda_1

xmax​R(A,x)=λn​xmin​R(A,x)=λ1​

瑞利商性质证明

瑞利商的上下界

由于A为对称矩阵，可以进行相似对角化：

A

=

U

Λ

U

T

A=U\Lambda U^T

A=UΛUT，其中特征对角阵

Λ

=

d

i

a

g

(

λ

1

,

λ

2

,

.

.

.

,

λ

n

)

\Lambda=diag(\lambda_1,\lambda_2,...,\lambda_n)

Λ=diag(λ1​,λ2​,...,λn​)，特征向量阵

U

=

(

v

1

,

v

2

,

.

.

.

,

v

n

)

U=(v_1,v_2,...,v_n)

U=(v1​,v2​,...,vn​)，且满足

U

U

T

=

I

UU^T=I

UUT=I。有：

R

(

A

,

x

)

=

x

T

A

x

x

T

x

=

x

T

U

Λ

U

T

x

x

T

U

U

T

x

R(A,x)=\frac{x^TAx}{x^Tx}=\frac{x^TU\Lambda U^Tx}{x^TUU^Tx}

R(A,x)=xTxxTAx​=xTUUTxxTUΛUTx​，令

y

=

U

T

x

y=U^Tx

y=UTx，有：

R

(

A

,

x

)

=

y

T

Λ

y

y

T

y

\begin{aligned} R(A,x)&=\frac{y^T\Lambda y}{y^Ty}\\ \end{aligned}

R(A,x)​=yTyyTΛy​​

∵

\because

∵

y

T

Λ

y

=

[

y

1

,

y

2

,

⋯

,

y

n

]

[

λ

1

λ

2

⋱

λ

n

]

[

y

1

y

2

⋮

y

n

]

=

∑

i

n

λ

i

y

i

2

y

y

T

=

[

y

1

,

y

2

,

⋯

,

y

n

]

[

y

1

y

2

⋮

y

n

]

=

∑

i

n

y

i

2

\begin{aligned} &y^T\Lambda y=[y_1,y_2,\cdots,y_n] \begin{bmatrix} \lambda_1 & & & \\ & \lambda_2 & & \\ & & \ddots & \\ & & & \lambda_n \\ \end{bmatrix} \begin{bmatrix} y_1\\ y_2\\ \vdots\\ y_n\\ \end{bmatrix}=\sum_i^n\lambda_iy_i^2 \\ &yy^T=[y_1,y_2,\cdots,y_n] \begin{bmatrix} y_1\\ y_2\\ \vdots\\ y_n\\ \end{bmatrix}=\sum_i^ny_i^2 \\ \end{aligned}

​yTΛy=[y1​,y2​,⋯,yn​]

​λ1​​λ2​​⋱​λn​​

​

​y1​y2​⋮yn​​

​=i∑n​λi​yi2​yyT=[y1​,y2​,⋯,yn​]

​y1​y2​⋮yn​​

​=i∑n​yi2​​

∴

\therefore

∴

R

(

A

,

x

)

=

∑

i

n

λ

i

y

i

2

∑

i

n

y

i

2

\begin{aligned} R(A,x)=\frac{\mathop{\sum}\limits_{i}^n \lambda_iy_i^2}{\mathop{\sum}\limits_{i}^n y_i^2} \end{aligned}

R(A,x)=i∑n​yi2​i∑n​λi​yi2​​​ 由于特征值大小关系

λ

1

≤

λ

2

≤

⋯

≤

λ

n

\lambda_1\le\lambda_2\le\cdots\le\lambda_n

λ1​≤λ2​≤⋯≤λn​，显然有：

λ

1

∑

i

n

y

i

2

≤

∑

i

n

λ

i

y

i

2

≤

λ

n

∑

i

n

y

i

2

\lambda_1\mathop{\sum}\limits_{i}^n y_i^2 \leq \mathop{\sum}\limits_{i}^n\lambda_i y_i^2 \leq \lambda_n \mathop{\sum}\limits_{i}^n y_i^2

λ1​i∑n​yi2​≤i∑n​λi​yi2​≤λn​i∑n​yi2​，于是有：

λ

1

∑

i

n

y

i

2

∑

i

n

y

i

2

≤

∑

i

n

λ

i

y

i

2

∑

i

n

y

i

2

≤

λ

n

∑

i

n

y

I

2

∑

i

n

y

i

2

\frac{\lambda_1\mathop{\sum}\limits_{i}^n y_i^2}{\mathop{\sum}\limits_{i}^n y_i^2} \leq \frac{\mathop{\sum}\limits_{i}^n\lambda_i y_i^2}{\mathop{\sum}\limits_{i}^n y_i^2} \leq \frac{\lambda_n \mathop{\sum}\limits_{i}^n y_I^2}{\mathop{\sum}\limits_{i}^n y_i^2}

i∑n​yi2​λ1​i∑n​yi2​​≤i∑n​yi2​i∑n​λi​yi2​​≤i∑n​yi2​λn​i∑n​yI2​​，即：

λ

1

≤

R

(

A

,

x

)

≤

λ

n

\lambda_1 \leq R(A,x) \leq \lambda_n

λ1​≤R(A,x)≤λn​

瑞利商的上下确界

上一节已经证明了瑞利商的范围为

[

λ

m

i

n

,

λ

m

a

x

]

[\lambda_{min}, \lambda_{max}]

[λmin​,λmax​]，要想知道上、下确界为

λ

m

i

n

,

λ

m

a

x

\lambda_{min}, \lambda_{max}

λmin​,λmax​，只需要寻找特殊值使

R

(

A

,

x

)

=

λ

1

R(A,x) = \lambda_1

R(A,x)=λ1​ 或

R

(

A

,

x

)

=

λ

n

R(A,x) = \lambda_n

R(A,x)=λn​ 即可。

由于

v

1

,

v

2

,

.

.

.

,

v

n

v_1,v_2,...,v_n

v1​,v2​,...,vn​ 是

n

n

n 维空间的一组单位正交基，因此可以设

n

n

n 维向量

x

=

∑

i

=

1

n

k

i

v

i

x=\sum_{i=1}^{n} k_iv_i

x=∑i=1n​ki​vi​，为简单起见，我们设

x

T

x

=

1

x^Tx=1

xTx=1。有：

y

=

U

T

x

=

[

v

1

T

v

2

T

⋮

v

n

T

]

(

k

1

v

+

k

2

v

2

+

⋯

+

k

n

v

n

)

=

[

k

1

k

2

⋮

k

n

]

y=U^Tx= \begin{bmatrix} v_1^T\\ v_2^T\\ \vdots\\ v_n^T\\ \end{bmatrix} (k_1v+k_2v_2+\cdots+k_nv_n)= \begin{bmatrix} k_1\\ k_2\\ \vdots\\ k_n\\ \end{bmatrix}

y=UTx=

​v1T​v2T​⋮vnT​​

​(k1​v+k2​v2​+⋯+kn​vn​)=

​k1​k2​⋮kn​​

​，所以有：

R

(

A

,

x

)

=

x

T

A

x

x

T

x

=

x

T

U

Λ

U

T

x

x

T

x

=

y

T

Λ

y

=

[

k

1

,

k

2

,

⋯

,

k

n

]

[

λ

1

λ

2

⋱

λ

n

]

[

k

1

k

2

⋮

k

n

]

=

∑

i

=

1

n

k

i

2

λ

i

\begin{aligned} R(A,x)&=\frac{x^TAx}{x^Tx} \\ &={\frac {x^TU\Lambda U^T x} {x^Tx}} \\ &=y^T\Lambda y\\ &=[k_1,k_2,\cdots,k_n] \begin{bmatrix} \lambda_1 & & & \\ & \lambda_2 & & \\ & & \ddots & \\ & & & \lambda_n \\ \end{bmatrix} \begin{bmatrix} k_1\\ k_2\\ \vdots\\ k_n\\ \end{bmatrix} \\ &=\sum_{i=1}^nk_i^2\lambda_i \end{aligned}

R(A,x)​=xTxxTAx​=xTxxTUΛUTx​=yTΛy=[k1​,k2​,⋯,kn​]

​λ1​​λ2​​⋱​λn​​

​

​k1​k2​⋮kn​​

​=i=1∑n​ki2​λi​​ 显然有：

λ

1

∑

i

=

1

n

k

i

2

≤

∑

i

=

1

n

k

i

2

λ

i

<

λ

n

∑

i

=

1

n

k

i

2

\lambda_1\sum_{i=1}^nk_i^2\le\sum_{i=1}^nk_i^2\lambda_i<\lambda_n\sum_{i=1}^nk_i^2

λ1​∑i=1n​ki2​≤∑i=1n​ki2​λi​<λn​∑i=1n​ki2​，即：

λ

1

≤

R

(

A

,

x

)

≤

λ

n

\lambda_1\le R(A,x)\le\lambda_n

λ1​≤R(A,x)≤λn​ 因为

R

(

A

,

x

)

=

∑

i

=

1

n

k

i

2

λ

i

=

k

1

2

λ

1

+

k

2

2

λ

2

+

⋯

+

k

n

2

λ

n

R(A,x)=\sum_{i=1}^nk_i^2\lambda_i=k_1^2\lambda_1+k_2^2\lambda_2+\cdots+k_n^2\lambda_n

R(A,x)=∑i=1n​ki2​λi​=k12​λ1​+k22​λ2​+⋯+kn2​λn​，

k

1

2

+

k

2

2

+

⋯

+

k

n

2

=

1

k_1^2+k_2^2+\cdots+k_n^2=1

k12​+k22​+⋯+kn2​=1，所以：

当

k

1

=

1

k_1=1

k1​=1时，

R

(

A

,

x

)

R(A,x)

R(A,x) 取最小值，即

λ

1

\lambda_1

λ1​;当

k

n

=

1

k_n=1

kn​=1时，

R

(

A

,

x

)

R(A,x)

R(A,x) 取最大值，即

λ

n

\lambda_n

λn​;

瑞利商的上下确界证毕。

■

\blacksquare

■

参考

https://sharmaeklavya2.github.io/theoremdep/nodes/linear-algebra/matrices/bounding-quadratic-form-using-eigenvalues.html https://www.cnblogs.com/spencergogo/p/16112581.html https://zhuanlan.zhihu.com/p/440760513