特征裂隙

矩阵论中,特征裂隙(eigen gap)指的是一组相邻的特征值(或奇异值)所构成的集合,与其它特征值(或奇异值)之间的豪斯多夫距离

特征裂隙的概念,一般只在矩阵的全部特征值(或奇异值)都是实数之语境下提出和研讨。

定义

假设矩阵   的特征值(或奇异值)都是实数,从大到小排序如下:  ,对任意给定的  ,考虑第   至第   个特征值(或奇异值)构成的集合  ,那么该集合   的特征裂隙定义为:

  [1]

其中为方便,不妨设  .

重要性

特征裂隙是对矩阵的线性子空间进行误差分析的基础。特征裂隙较大的  ,其对应的特征向量所张成的线性子空间,在矩阵元素被误差项(往往是随机误差)所污染时,具有较好的稳定性。[2]反之,若特征裂隙为0,则由线性代数知,   对应的特征向量所张成的线性子空间不是唯一的。特征裂隙较小的   不具有抗拒随机误差的稳定性。

机器学习中,对谱分类英语Spectral clustering算法的理论性质进行研究时,建立足够的特征裂隙一般来说属于理论分析的核心部分。[3][4]

需要注意的是,如果目标是估计矩阵的线性子空间,那么特征裂隙具有核心的重要地位。但如果目标是为矩阵本身降噪,那么特征裂隙是不重要的,流行的矩阵估计方法也并不需要任何特征裂隙条件。[5][6][7]

参见

参考文献

  1. ^ Yu, Y.; Wang, T.; Samworth, R. J. A useful variant of the Davis–Kahan theorem for statisticians. Biometrika. 2015-06, 102 (2): 315–323. ISSN 0006-3444. doi:10.1093/biomet/asv008 (英语). 
  2. ^ Lei, Jing; Rinaldo, Alessandro. Consistency of spectral clustering in stochastic block models. The Annals of Statistics. 2015-02-01, 43 (1) [2021-12-14]. ISSN 0090-5364. doi:10.1214/14-AOS1274. (原始内容存档于2021-12-14). 
  3. ^ Qin, Tai; Rohe, Karl. Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel. NIPS. 2013-09-16 [2021-12-14]. arXiv:1309.4111 . (原始内容存档于2021-12-14). 
  4. ^ Xia, Dong. Confidence Region of Singular Subspaces for Low-Rank Matrix Regression. IEEE Transactions on Information Theory. 2019-11, 65 (11): 7437–7459 [2021-12-14]. ISSN 0018-9448. doi:10.1109/TIT.2019.2924900. (原始内容存档于2021-12-14). 
  5. ^ Chatterjee, Sourav. Matrix estimation by Universal Singular Value Thresholding. The Annals of Statistics. 2015-02-01, 43 (1) [2021-12-14]. ISSN 0090-5364. doi:10.1214/14-AOS1272. (原始内容存档于2021-12-14). 
  6. ^ Gao, Chao; Lu, Yu; Zhou, Harrison H. Rate-optimal graphon estimation. The Annals of Statistics. 2015-12-01, 43 (6) [2021-12-14]. ISSN 0090-5364. doi:10.1214/15-AOS1354. (原始内容存档于2021-12-14). 
  7. ^ Zhang, Yuan; Levina, Elizaveta; Zhu, Ji. Estimating network edge probabilities by neighbourhood smoothing. Biometrika. 2017-12-01, 104 (4): 771–783. ISSN 0006-3444. doi:10.1093/biomet/asx042 (英语).