前言
在推导标准化拉普拉斯矩阵的特征值范围时,用到了瑞利商,它也是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
xmaxR(A,x)=λnxminR(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
y1y2⋮yn
=i∑nλiyi2yyT=[y1,y2,⋯,yn]
y1y2⋮yn
=i∑nyi2
∴
\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∑nyi2i∑nλiyi2 由于特征值大小关系
λ
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
λ1i∑nyi2≤i∑nλiyi2≤λni∑nyi2,于是有:
λ
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∑nyi2λ1i∑nyi2≤i∑nyi2i∑nλiyi2≤i∑nyi2λni∑nyI2,即:
λ
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=1nkivi,为简单起见,我们设 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=
v1Tv2T⋮vnT
(k1v+k2v2+⋯+knvn)=
k1k2⋮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
k1k2⋮kn
=i=1∑nki2λ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=1nki2≤∑i=1nki2λi<λn∑i=1nki2,即:
λ
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=1nki2λ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://www.toymoban.com/news/detail-433163.html
参考
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文章来源地址https://www.toymoban.com/news/detail-433163.html
到了这里,关于瑞利商性质及证明的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!