查看“︁Davis-Kahan定理”︁的源代码

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

==定理内容==

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

:<math>\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)</math>

上式中，“<math>\Theta</math>”是一个数学运算，表示线性空间之间的张角。

===定理的经典版本===
有了线性空间之间张角的定义，便可以开始陈述定理内容。设 <math>\Sigma,\hat{\Sigma} \in\mathbb{R}^{p\times p}</math>是两个对称的随机矩阵，其特征值记为 <math>\lambda_1\geq\cdots\geq\lambda_p</math> 和 <math>\hat\lambda_1\geq\cdots\geq\hat\lambda_p</math>。对任何 <math>(r,s):1\leq r\leq s\leq p</math> ，考虑第 <math>\{\lambda_r,\ldots,\lambda_s\}</math> 这总共 <math>s-r+1</math> 个特征值之对应的特征向量所张成的线性子空间，将它记为 <math>V</math>，类似地定义 <math>\hat{V}</math>。

下面定义定理中最重要的量，即'''特征裂隙''' <math>\delta</math>：
:<math> \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\} </math>

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

:<math>\|\sin\Theta(\hat V,V)\|_F  \leq \frac{\|\hat\Sigma-\Sigma\|_F}{\delta}</math>

其中 <math>\|\cdot\|_F</math> 表示[[矩陣範數#弗罗贝尼乌斯范数|Frobenius范数]]，即将矩阵的所有元素平方求和后，再开根号。{{r|Stewart-Sun}}

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

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

:<math>\min(\lambda_{r-1}-\lambda_r, \lambda_s-\lambda_{s+1}) >0</math>

Yu-Wang-Samworth定理的结论，按经典版的 <math>\sin\Theta</math> 语言，陈述如下：

:<math>\|\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})}</math>

其中，<math>\|\cdot\|</math> 表示矩阵的谱范数，即其最大奇异值。

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

:<math>\|\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})}</math>

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

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

==参见==

[[特征裂隙]]

==参考文献==
{{reflist|refs=

<ref name=Stewart-Sun>{{cite book |author1=G. Stewart |author2=Ji-Guang Sun |title=Matrix perturbation theory |publisher=Academic Press |isbn=9780126702309}}</ref>

<ref name=Yu-Wang-Samworth>{{cite journal |last1=Yu |first1=Y. |last2=Wang |first2=T. |last3=Samworth |first3=R. J. |title=A useful variant of the Davis–Kahan theorem for statisticians |journal=Biometrika |date=2015-06 |volume=102 |issue=2 |pages=315–323 |doi=10.1093/biomet/asv008}}</ref>

<ref name=Rohe-Chatterjee-Yu>{{cite journal |last1=Rohe |first1=Karl |last2=Chatterjee |first2=Sourav |last3=Yu |first3=Bin |title=Spectral clustering and the high-dimensional stochastic blockmodel |url=https://archive.org/details/sim_annals-of-statistics_2011-08_39_4/page/1878 |journal=The Annals of Statistics |date=2011-08 |volume=39 |issue=4 |pages=1878–1915 |doi=10.1214/11-AOS887}}</ref>

<ref name=Lei-Rinaldo>{{cite journal |last1=Lei |first1=Jing |last2=Rinaldo |first2=Alessandro |title=Consistency of spectral clustering in stochastic block models |journal=The Annals of Statistics |date=2015-02 |volume=43 |issue=1 |pages=215–237 |doi=10.1214/14-AOS1274}}</ref>

}}

[[Category:数学定理|D]]
[[Category:矩陣]]
[[Category:机器学习]]
[[Category:线性代数定理]]