跳至內容

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.