Davis-Kahan定理

Davis-Kahan定理（Davis-Kahan theorem）是随机矩阵分析中的一个重要的基础性定理。它的基本内容是，如果两个矩阵在某种合适的模之下相近，且有足够的特征裂隙，那么它们相应的特征向量子空间也相似。

定理内容

两个线性空间的夹角

考虑两个单位列正交矩阵 $V,\hat{V}\in {ℝ}^{n\times d}$ （“单位列正交”意为：其满足 $V^{T}V={\hat{V}}^T\hat{V}=I_d$） 之列向量分别张成的线性子空间，那么这两个子空间的张角，是由一个矩阵所表示的（显然这是如下熟知的特殊情形之概念上的拓展： $d=1$ 时，通常用一个数值表示两个向量之间的张角），式子如下：

$\mathrm{\Theta }(V,\hat{V})=\mathrm{D}\mathrm{i}\mathrm{a}\mathrm{g}\mathrm{o}\mathrm{n}\mathrm{a}\mathrm{l}(\arccos ⟨V_{\cdot 1},{\hat{V}}_{\cdot 1}⟩,\dots ,\arccos ⟨V_{\cdot d},{\hat{V}}_{\cdot d}⟩)$

上式中，“$\mathrm{\Theta }$”是一个数学运算，表示线性空间之间的张角。

定理的经典版本

有了线性空间之间张角的定义，便可以开始陈述定理内容。设 $\mathrm{\Sigma },\hat{\mathrm{\Sigma }}\in {ℝ}^{p\times p}$是两个对称的随机矩阵，其特征值记为 ${\lambda }_1\ge \cdots \ge {\lambda }_p$ 和 ${\hat{\lambda }}_1\ge \cdots \ge {\hat{\lambda }}_p$。对任何 $(r,s):1\le r\le s\le p$ ，考虑第 $\{{\lambda }_r,\dots ,{\lambda }_s\}$ 这总共 $s-r+1$ 个特征值之对应的特征向量所张成的线性子空间，将它记为 $V$，类似地定义 $\hat{V}$。

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

$\delta =\inf \{|\hat{\lambda }-\lambda |:\lambda \in [{\lambda }_s,{\lambda }_r],\hat{\lambda }\in (-\mathrm{\infty },{\hat{\lambda }}_{s+1}]\cup [{\hat{\lambda }}_{r-1},\mathrm{\infty })\}$

定理的结论是，如果 $\delta >0$ ，那么有如下不等式：

$\Vert \sin \mathrm{\Theta }(\hat{V},V){\Vert }_F\le \frac{\Vert \hat{\mathrm{\Sigma }}-\mathrm{\Sigma }{\Vert }_F}{\delta }$

其中 $\Vert \cdot {\Vert }_F$ 表示Frobenius范数，即将矩阵的所有元素平方求和后，再开根号。Template:R

定理的Yu-Wang-Samworth变体版本

Davis-Kahan定理的经典版本有一些可改进之处，主要在于正特征裂隙假设，是一个同时牵涉两个矩阵的特征值 $\lambda$ 和 $\hat{\lambda }$ 的条件，这对其应用的方便性造成负面影响。余怡、王腾耀和Richard Samworth于2014年发现如下变体Template:R，其最大特色是其只需其中一个矩阵满足正特征裂隙条件。

沿用上面经典版本定理的记号，另记 $d=s-r+1$ ，并用如下的特征裂隙条件代替原定理中的 $\delta >0$：

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

Yu-Wang-Samworth定理的结论，按经典版的 $\sin \mathrm{\Theta }$ 语言，陈述如下：

$\Vert \sin \mathrm{\Theta }(\hat{V},V){\Vert }_F\le \frac{2\min (d^{1/2}\Vert \hat{\mathrm{\Sigma }}-\mathrm{\Sigma }\Vert ,\Vert \hat{\mathrm{\Sigma }}-\mathrm{\Sigma }{\Vert }_F)}{\min ({\lambda }_{r-1}-{\lambda }_r,{\lambda }_s-{\lambda }_{s+1})}$

其中，$\Vert \cdot \Vert$ 表示矩阵的谱范数，即其最大奇异值。

进一步，按矩阵论语言，有如下更显式的结论：存在一个正交矩阵 $\hat{O}\in {ℝ}^{d\times d}$ （“正交”是指其满足 $O^{T}O=I_d$），使得：

$\Vert \hat{V}\hat{O}-V{\Vert }_F\le \frac{2^{3/2}\min (d^{1/2}\Vert \hat{\mathrm{\Sigma }}-\mathrm{\Sigma }\Vert ,\Vert \hat{\mathrm{\Sigma }}-\mathrm{\Sigma }{\Vert }_F)}{\min ({\lambda }_{r-1}-{\lambda }_r,{\lambda }_s-{\lambda }_{s+1})}$

注意事项

虽然Davis-Kahan定理大多数的应用是套用到随机矩阵上，但要注意定理本身并不局限于随机矩阵，无论定理内容中出现的矩阵是常数矩阵还是随机矩阵（抑或是一个确定一个随机），只要假设条件满足，定理的结论都成立（而非仅以大概率成立或渐近成立）。

应用

Davis-Kahan定理拥有广泛的应用，是谱聚类方法的理论基础，在统计学习和统计网络分析的很多涉及聚类问题的研究中，占据重要地位。Template:RTemplate:R

参见

特征裂隙