Universality for eigenvalue algorithms on sample covariance matrices

2017/01/07 by Percy Deift, Deift, Percy, Thomas Trogdon +1
Mathematics · #15B52 #65L15 #70H06 #Advanced Algebra and Geometry #Advanced Combinatorial Mathematics #FOS: Mathematics #Numerical Analysis (math.NA) #Probability (math.PR) #Random Matrices and Applications

paper · pdf · doi:10.48550/arxiv.1701.01896

openalex publication_date 2017/01/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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).

Citations

• On the distribution of the largest eigenvalue in principal components analysis
• The QR Transformation A Unitary Analogue to the LR Transformation--Part 1
• Universality for the Toda algorithm to compute the largest eigenvalue of\n a random matrix

Related

• Universality for the Toda algorithm to compute the largest eigenvalue of\n a random matrix
• Random covariance matrices: Universality of local statistics of eigenvalues up to the edge
• Universality for the largest eigenvalue of sample covariance matrices with general population
• Quantitative Universality for the Largest Eigenvalue of Sample Covariance Matrices
• How long does it take to compute the eigenvalues of a random symmetric matrix?