Universality for Eigenvalue Algorithms on Sample Covariance Matrices

DOI10.1137/17M1110900zbMATH Open1378.65089arXiv1701.01896MaRDI QIDQ4594907FDOQ4594907

Authors: Thomas Trogdon, Percy A. Deift 

Publication date: 27 November 2017

Published in: SIAM Journal on Numerical Analysis (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1701.01896

Recommendations

• Universality for the largest eigenvalue of sample covariance matrices with general population
• A universality result for the smallest eigenvalues of certain sample covariance matrices
• Universality of local eigenvalue statistics for some sample covariance matrices
• Universality results for the largest eigenvalues of some sample covariance matrix ensembles
• On the eigenvectors of large dimensional sample covariance matrices
• scientific article; zbMATH DE number 3940318
• A note on universality of the distribution of the largest eigenvalues in certain sample covariance matrices
• Universality for the Conjugate Gradient and MINRES Algorithms on Sample Covariance Matrices
• Universality of covariance matrices
• Random covariance matrices: universality of local statistics of eigenvalues

zbMATH Keywords

random matrixalgorithmcovariance matriceseigenvectoruniversalitycomplexity estimateeigenvalue computationuniversal limit theoremQR eigenvalue algorithminverse power methods

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Numerical computation of eigenvalues and eigenvectors of matrices (65F15)

Cites Work

• On the distribution of the largest eigenvalue in principal components analysis
• DISTRIBUTION OF EIGENVALUES FOR SOME SETS OF RANDOM MATRICES
• Title not available (Why is that?)
• Limiting spectral distribution for a class of random matrices
• Shape fluctuations and random matrices
• Beta ensembles, stochastic Airy spectrum, and a diffusion
• The spectrum edge of random matrix ensembles.
• On the condition number of the critically-scaled Laguerre unitary ensemble
• Universality in numerical computations with random data
• Eigenvalues and Condition Numbers of Random Matrices
• Numerical Inverting of Matrices of High Order. II
• On asymptotics of eigenvectors of large sample covariance matrix
• Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
• Universality of local eigenvalue statistics for some sample covariance matrices
• Universality of covariance matrices
• Ordinary Differential Equations and the Symmetric Eigenvalue Problem
• A limit theorem for the norm of random matrices
• The smallest eigenvalue of a large dimensional Wishart matrix
• The simplex method. A probabilistic analysis
• The strong limits of random matrix spectra for sample matrices of independent elements
• The QR Transformation A Unitary Analogue to the LR Transformation--Part 1
• Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time
• On the efficiency of algorithms of analysis
• How long does it take to compute the eigenvalues of a random symmetric matrix?
• Smoothed analysis of binary search trees
• On the principal components of sample covariance matrices
• Joint distribution of the first and second eigenvalues at the soft edge of unitary ensembles
• Universality for the Toda algorithm to compute the largest eigenvalue of a random matrix
• Isospectral Flows
• Complexity theory of numerical linear algebra
• Universal halting times in optimization and machine learning
• Smoothed analysis for the conjugate gradient algorithm

Cited In (11)

• Mini-workshop: Reflectionless operators: the Deift and Simon conjectures. Abstracts from the mini-workshop held October 22--28, 2017
• Universality for the Toda algorithm to compute the largest eigenvalue of a random matrix
• Universality for the Conjugate Gradient and MINRES Algorithms on Sample Covariance Matrices
• Universal halting times in optimization and machine learning
• The conjugate gradient algorithm on a general class of spiked covariance matrices
• How long does it take to compute the eigenvalues of a random symmetric matrix?
• Universality in numerical computations with random data
• Universality in numerical computation with random data: case studies and analytical results
• Universal statistics of incubation periods and other detection times via diffusion models
• Some open problems in random matrix theory and the theory of integrable systems. II
• Three lectures on ``Fifty years of KdV: an integrable system

Uses Software

• numericaluniversality

This page was built for publication: Universality for Eigenvalue Algorithms on Sample Covariance Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4594907)