Universality for Eigenvalue Algorithms on Sample Covariance Matrices

DOI10.1137/17M1110900MaRDI QIDQ4594907zbMATH OpenFDO

Authors Thomas Trogdon, Percy A. Deift

Publication date 27 November 2017

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

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

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)

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

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

Cites work

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

Cited in

(11)

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

Describes a project that uses

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)