Universality for Eigenvalue Algorithms on Sample Covariance Matrices
Universality for Eigenvalue Algorithms on Sample Covariance Matrices
复制标题
样本协方差矩阵特征值算法的普适性
DOI：
10.1137/17m1110900
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
T. Trogdon
中科院分区：
文献类型：
--
作者：
P. Deift;T. Trogdon
我们证明了幂/逆幂方法和QR特征值算法的停止时间或迭代次数的一个通用极限定理。具体来说，我们分析了在规定公差范围内计算随机正定样本协方差矩阵的极端特征值所需的迭代次数。通用性定理为算法的复杂度估计提供了一个估计，在这个随机设置下，这些算法有高概率成立。证明方法依赖于随机样本协方差矩阵的特征值和特征向量统计的最新结果（即，离域，刚性和边缘普遍性）。
We prove a universal limit theorem for the halting time, or iteration count, of the power/inverse power methods and the QR eigenvalue algorithm. Specifically, we analyze the required number of iterations to compute extreme eigenvalues of random, positive definite sample covariance matrices to within a prescribed tolerance. The universality theorem provides a complexity estimate for the algorithms which, in this random setting, holds with high probability. The method of proof relies on recent results on the statistics of the eigenvalues and eigenvectors of random sample covariance matrices (i.e., delocalization, rigidity, and edge universality).
Toda 算法计算随机矩阵最大特征值的通用性
影响因子：
3
作者：
Deift, Percy;Trogdon, Thomas
通讯作者：
Trogdon, Thomas