Davis-Kahan定理

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

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

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

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

下面定义定理中最重要的量，即特征裂隙 ${\displaystyle \mathrm{\delta <!--\; \delta \; -->}}$：

定理的结论是，如果 ${\displaystyle \mathrm{\delta <!--\; \delta \; -->}>0}$ ，那么有如下不等式：

其中 ${\displaystyle \Vert <!--\; \Vert \; -->\cdot <!--\; \cdot \; -->{\Vert <!--\; \Vert \; -->}_F}$ 表示Frobenius范数，即将矩阵的所有元素平方求和后，再开根号。

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

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

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

其中，${\displaystyle \Vert <!--\; \Vert \; -->\cdot <!--\; \cdot \; -->\Vert <!--\; \Vert \; -->}$ 表示矩阵的谱范数，即其最大奇异值。

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

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

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

特征裂隙