Davis-Kahan定理

Davis-Kahan定理（Davis-Kahan theorem）是隨機矩陣分析中的一個重要的基礎性定理。它的基本內容是，如果兩個矩陣在某種合適的模之下相近，且有足夠的特徵裂隙，那麼它們相應的特徵向量子空間也相似。

定理內容

兩個線性空間的夾角

考慮兩個單位列正交矩陣 $V,{\hat {V}}\in \mathbb {R} ^{n\times d}$ （「單位列正交」意為：其滿足 $V^{T}V={\hat {V}}^{T}{\hat {V}}=I_{d}$） 之列向量分別張成的線性子空間，那麼這兩個子空間的張角，是由一個矩陣所表示的（顯然這是如下熟知的特殊情形之概念上的拓展： $d=1$ 時，通常用一個數值表示兩個向量之間的張角），式子如下：

$\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 )$

上式中，「$\Theta$」是一個數學運算，表示線性空間之間的張角。

定理的經典版本

有了線性空間之間張角的定義，便可以開始陳述定理內容。設 $\Sigma ,{\hat {\Sigma }}\in \mathbb {R} ^{p\times p}$是兩個對稱的隨機矩陣，其特徵值記為 $\lambda _{1}\geq \cdots \geq \lambda _{p}$ 和 ${\hat {\lambda }}_{1}\geq \cdots \geq {\hat {\lambda }}_{p}$。對任何 $(r,s):1\leq r\leq s\leq p$ ，考慮第 $\{\lambda _{r},\ldots ,\lambda _{s}\}$ 這總共 $s-r+1$ 個特徵值之對應的特徵向量所張成的線性子空間，將它記為 $V$，類似地定義 ${\hat {V}}$。

下面定義定理中最重要的量，即特徵裂隙 $\delta$：

$\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\}$

定理的結論是，如果 $\delta >0$ ，那麼有如下不等式：

$\|\sin \Theta ({\hat {V}},V)\|_{F}\leq {\frac {\|{\hat {\Sigma }}-\Sigma \|_{F}}{\delta }}$

其中 $\|\cdot \|_{F}$ 表示Frobenius範數，即將矩陣的所有元素平方求和後，再開根號。

定理的Yu-Wang-Samworth變體版本

Davis-Kahan定理的經典版本有一些可改進之處，主要在於正特徵裂隙假設，是一個同時牽涉兩個矩陣的特徵值 $\lambda$ 和 ${\hat {\lambda }}$ 的條件，這對其應用的方便性造成負面影響。余怡、王騰耀和Richard Samworth於2014年發現如下變體，其最大特色是其只需其中一個矩陣滿足正特徵裂隙條件。

沿用上面經典版本定理的記號，另記 $d=s-r+1$ ，並用如下的特徵裂隙條件代替原定理中的 $\delta >0$：

$\min(\lambda _{r-1}-\lambda _{r},\lambda _{s}-\lambda _{s+1})>0$

Yu-Wang-Samworth定理的結論，按經典版的 $\sin \Theta$ 語言，陳述如下：

$\|\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})}}$

其中，$\|\cdot \|$ 表示矩陣的譜範數，即其最大奇異值。

進一步，按矩陣論語言，有如下更顯式的結論：存在一個正交矩陣 ${\hat {O}}\in \mathbb {R} ^{d\times d}$ （「正交」是指其滿足 $O^{T}O=I_{d}$），使得：

$\|{\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定理擁有廣泛的應用，是譜聚類方法的理論基礎，在統計學習和統計網絡分析的很多涉及聚類問題的研究中，佔據重要地位。

參見

特徵裂隙