Davis-Kahan定理(Davis-Kahan theorem) 是隨機矩陣分析中的一個重要的基礎性定理。它的基本內容是,如果兩個矩陣在某種合適的模之下相近,且有足夠的特徵裂隙 ,那麼它們相應的特徵向量子空間也相似。
考慮兩個單位列正交矩陣
V
,
V
^
∈
R
n
×
d
{\displaystyle V,{\hat {V}}\in \mathbb {R} ^{n\times d}}
(「單位列正交」意為:其滿足
V
T
V
=
V
^
T
V
^
=
I
d
{\displaystyle V^{T}V={\hat {V}}^{T}{\hat {V}}=I_{d}}
) 之列向量分別張成的線性子空間,那麼這兩個子空間的張角,是由一個矩陣所表示的(顯然這是如下熟知的特殊情形之概念上的拓展:
d
=
1
{\displaystyle d=1}
時,通常用一個數值表示兩個向量之間的張角),式子如下:
Θ
(
V
,
V
^
)
=
D
i
a
g
o
n
a
l
(
arccos
⟨
V
⋅
1
,
V
^
⋅
1
⟩
,
…
,
arccos
⟨
V
⋅
d
,
V
^
⋅
d
⟩
)
{\displaystyle \Theta (V,{\hat {V}})=\mathrm {Diagonal} (\arccos \langle V_{\cdot 1},{\hat {V}}_{\cdot 1}\rangle ,\ldots ,\arccos \langle V_{\cdot d},{\hat {V}}_{\cdot d}\rangle )}
上式中,「
Θ
{\displaystyle \Theta }
」是一個數學運算,表示線性空間之間的張角。
有了線性空間之間張角的定義,便可以開始陳述定理內容。設
Σ
,
Σ
^
∈
R
p
×
p
{\displaystyle \Sigma ,{\hat {\Sigma }}\in \mathbb {R} ^{p\times p}}
是兩個對稱的隨機矩陣,其特徵值記為
λ
1
≥
⋯
≥
λ
p
{\displaystyle \lambda _{1}\geq \cdots \geq \lambda _{p}}
和
λ
^
1
≥
⋯
≥
λ
^
p
{\displaystyle {\hat {\lambda }}_{1}\geq \cdots \geq {\hat {\lambda }}_{p}}
。對任何
(
r
,
s
)
:
1
≤
r
≤
s
≤
p
{\displaystyle (r,s):1\leq r\leq s\leq p}
,考慮第
{
λ
r
,
…
,
λ
s
}
{\displaystyle \{\lambda _{r},\ldots ,\lambda _{s}\}}
這總共
s
−
r
+
1
{\displaystyle s-r+1}
個特徵值之對應的特徵向量所張成的線性子空間,將它記為
V
{\displaystyle V}
,類似地定義
V
^
{\displaystyle {\hat {V}}}
。
下面定義定理中最重要的量,即特徵裂隙
δ
{\displaystyle \delta }
:
δ
=
inf
{
|
λ
^
−
λ
|
:
λ
∈
[
λ
s
,
λ
r
]
,
λ
^
∈
(
−
∞
,
λ
^
s
+
1
]
∪
[
λ
^
r
−
1
,
∞
)
}
{\displaystyle \delta =\inf \left\{|{\hat {\lambda }}-\lambda |:\lambda \in [\lambda _{s},\lambda _{r}],{\hat {\lambda }}\in (-\infty ,{\hat {\lambda }}_{s+1}]\cup [{\hat {\lambda }}_{r-1},\infty )\right\}}
定理的結論是,如果
δ
>
0
{\displaystyle \delta >0}
,那麼有如下不等式:
‖
sin
Θ
(
V
^
,
V
)
‖
F
≤
‖
Σ
^
−
Σ
‖
F
δ
{\displaystyle \|\sin \Theta ({\hat {V}},V)\|_{F}\leq {\frac {\|{\hat {\Sigma }}-\Sigma \|_{F}}{\delta }}}
其中
‖
⋅
‖
F
{\displaystyle \|\cdot \|_{F}}
表示Frobenius範數 ,即將矩陣的所有元素平方求和後,再開根號。[ 1]
定理的Yu-Wang-Samworth變體版本
編輯
Davis-Kahan定理的經典版本有一些可改進之處,主要在於正特徵裂隙假設,是一個同時牽涉兩個矩陣的特徵值
λ
{\displaystyle \lambda }
和
λ
^
{\displaystyle {\hat {\lambda }}}
的條件,這對其應用的方便性造成負面影響。余怡、王騰耀和Richard Samworth於2014年發現如下變體[ 2] ,其最大特色是其只需其中一個矩陣滿足正特徵裂隙條件。
沿用上面經典版本定理的記號,另記
d
=
s
−
r
+
1
{\displaystyle d=s-r+1}
,並用如下的特徵裂隙條件代替原定理中的
δ
>
0
{\displaystyle \delta >0}
:
min
(
λ
r
−
1
−
λ
r
,
λ
s
−
λ
s
+
1
)
>
0
{\displaystyle \min(\lambda _{r-1}-\lambda _{r},\lambda _{s}-\lambda _{s+1})>0}
Yu-Wang-Samworth定理的結論,按經典版的
sin
Θ
{\displaystyle \sin \Theta }
語言,陳述如下:
‖
sin
Θ
(
V
^
,
V
)
‖
F
≤
2
min
(
d
1
/
2
‖
Σ
^
−
Σ
‖
,
‖
Σ
^
−
Σ
‖
F
)
min
(
λ
r
−
1
−
λ
r
,
λ
s
−
λ
s
+
1
)
{\displaystyle \|\sin \Theta ({\hat {V}},V)\|_{F}\leq {\frac {2\min \left(d^{1/2}\|{\hat {\Sigma }}-\Sigma \|,\|{\hat {\Sigma }}-\Sigma \|_{F}\right)}{\min(\lambda _{r-1}-\lambda _{r},\lambda _{s}-\lambda _{s+1})}}}
其中,
‖
⋅
‖
{\displaystyle \|\cdot \|}
表示矩陣的譜範數,即其最大奇異值。
進一步,按矩陣論語言,有如下更顯式的結論:存在一個正交矩陣
O
^
∈
R
d
×
d
{\displaystyle {\hat {O}}\in \mathbb {R} ^{d\times d}}
(「正交」是指其滿足
O
T
O
=
I
d
{\displaystyle O^{T}O=I_{d}}
),使得:
‖
V
^
O
^
−
V
‖
F
≤
2
3
/
2
min
(
d
1
/
2
‖
Σ
^
−
Σ
‖
,
‖
Σ
^
−
Σ
‖
F
)
min
(
λ
r
−
1
−
λ
r
,
λ
s
−
λ
s
+
1
)
{\displaystyle \|{\hat {V}}{\hat {O}}-V\|_{F}\leq {\frac {2^{3/2}\min \left(d^{1/2}\|{\hat {\Sigma }}-\Sigma \|,\|{\hat {\Sigma }}-\Sigma \|_{F}\right)}{\min(\lambda _{r-1}-\lambda _{r},\lambda _{s}-\lambda _{s+1})}}}
雖然Davis-Kahan定理大多數的應用是套用到隨機矩陣上,但要注意定理本身並不局限於隨機矩陣,無論定理內容中出現的矩陣是常數矩陣還是隨機矩陣(抑或是一個確定一個隨機),只要假設條件滿足,定理的結論都成立(而非僅以大概率成立或漸近成立)。
Davis-Kahan定理擁有廣泛的應用,是譜聚類 方法的理論基礎,在統計學習和統計網絡分析的很多涉及聚類問題的研究中,佔據重要地位。[ 3] [ 4]
^ G. Stewart; Ji-Guang Sun. Matrix perturbation theory. Academic Press. ISBN 9780126702309 .
^ Yu, Y.; Wang, T.; Samworth, R. J. A useful variant of the Davis–Kahan theorem for statisticians. Biometrika. 2015-06, 102 (2): 315–323. doi:10.1093/biomet/asv008 .
^ Rohe, Karl; Chatterjee, Sourav; Yu, Bin. Spectral clustering and the high-dimensional stochastic blockmodel . The Annals of Statistics. 2011-08, 39 (4): 1878–1915. doi:10.1214/11-AOS887 .
^ Lei, Jing; Rinaldo, Alessandro. Consistency of spectral clustering in stochastic block models. The Annals of Statistics. 2015-02, 43 (1): 215–237. doi:10.1214/14-AOS1274 .