Davis-Kahan定理

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

定理内容

两个线性空间的夹角

考虑两个单位列正交矩阵   (“单位列正交”意为:其满足  ) 之列向量分别张成的线性子空间,那么这两个子空间的张角,是由一个矩阵所表示的(显然这是如下熟知的特殊情形之概念上的拓展:   时,通常用一个数值表示两个向量之间的张角),式子如下:

 

上式中,“ ”是一个数学运算,表示线性空间之间的张角。

定理的经典版本

有了线性空间之间张角的定义,便可以开始陈述定理内容。设  是两个对称的随机矩阵,其特征值记为   。对任何   ,考虑第   这总共   个特征值之对应的特征向量所张成的线性子空间,将它记为  ,类似地定义  

下面定义定理中最重要的量,即特征裂隙  

 

定理的结论是,如果   ,那么有如下不等式:

 

其中   表示Frobenius范数,即将矩阵的所有元素平方求和后,再开根号。[1]

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

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

沿用上面经典版本定理的记号,另记   ,并用如下的特征裂隙条件代替原定理中的  

 

Yu-Wang-Samworth定理的结论,按经典版的   语言,陈述如下:

 

其中,  表示矩阵的谱范数,即其最大奇异值。

进一步,按矩阵论语言,有如下更显式的结论:存在一个正交矩阵   (“正交”是指其满足  ),使得:

 

注意事项

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

应用

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

参见

特征裂隙

参考文献

  1. ^ G. Stewart; Ji-Guang Sun. Matrix perturbation theory. Academic Press. ISBN 9780126702309. 
  2. ^ 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. 
  3. ^ 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. 
  4. ^ 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.