The conjugate gradient algorithm on a general class of spiked covariance matrices
From MaRDI portal
Abstract: We consider the conjugate gradient algorithm applied to a general class of spiked sample covariance matrices. The main result of the paper is that the norms of the error and residual vectors at any finite step concentrate on deterministic values determined by orthogonal polynomials with respect to a deformed Marchenko--Pastur law. The first-order limits and fluctuations are shown to be universal. Additionally, for the case where the bulk eigenvalues lie in a single interval we show a stronger universality result in that the asymptotic rate of convergence of the conjugate gradient algorithm only depends on the support of the bulk, provided the spikes are well-separated from the bulk. In particular, this shows that the classical condition number bound for the conjugate gradient algorithm is pessimistic for spiked matrices.
Recommendations
- The conjugate gradient algorithm on well-conditioned Wishart matrices is almost deterministic
- Smoothed analysis for the conjugate gradient algorithm
- On the real convergence rate of the conjugate gradient method
- Spiked sample covariance matrices with possibly multiple bulk components
- Convergence of sample eigenvectors of spiked population model
Cites work
- A necessary and sufficient condition for edge universality at the largest singular values of covariance matrices
- A Riemann-Hilbert approach to asymptotic problems arising in the theory of random matrix models, and also in the theory of integrable statistical mechanics
- Analysis of the limiting spectral distribution of large dimensional random matrices
- Anisotropic local laws for random matrices
- Asymptotics of sample eigenstructure for a large dimensional spiked covariance model
- Average-Case Stability of Gaussian Elimination
- Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences
- Bounds for the Determinant of the Sum of Hermitian Matrices
- Convergence of eigenvector empirical spectral distribution of sample covariance matrices
- Convergence rates of eigenvector empirical spectral distribution of large dimensional sample covariance matrix
- DISTRIBUTION OF EIGENVALUES FOR SOME SETS OF RANDOM MATRICES
- Eigenvalue distributions of large Hermitian matrices; Wigner's semi- circle law and a theorem of Kac, Murdock, and Szegö
- Eigenvalues and Condition Numbers of Random Matrices
- Error Analysis of the Lanczos Algorithm for Tridiagonalizing a Symmetric Matrix
- Estimation of the Number of Spiked Eigenvalues in a Covariance Matrix by Bulk Eigenvalue Matching Analysis
- How long does it take to compute the eigenvalues of a random symmetric matrix?
- scientific article; zbMATH DE number 3477793 (Why is no real title available?)
- scientific article; zbMATH DE number 1012640 (Why is no real title available?)
- scientific article; zbMATH DE number 1996432 (Why is no real title available?)
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- Krylov subspace methods. Principles and analysis.
- Large sample covariance matrices and high-dimensional data analysis
- Limits of spiked random matrices. I
- Matrix models for beta ensembles
- Methods of conjugate gradients for solving linear systems
- Numerical Inverting of Matrices of High Order. II
- Nuttall's theorem with analytic weights on algebraic S-contours
- On asymptotics of eigenvectors of large sample covariance matrix
- On the asymptotic analysis of the Painleve equations via the isomonodromy method
- On the distribution of the largest eigenvalue in principal components analysis
- On the principal components of sample covariance matrices
- Orthogonal polynomials on several intervals: accumulation points of recurrence coefficients and of zeros
- Outliers in the spectrum of large deformed unitarily invariant models
- Random matrix theory in statistics: a review
- Riemann-Hilbert problems, their numerical solution, and the computation of nonlinear special functions
- Scattering Theory, Orthogonal Polynomials, andq-Series
- Smoothed analysis of algorithms
- Solution of Sparse Indefinite Systems of Linear Equations
- Spectral analysis of large dimensional random matrices
- Spiked sample covariance matrices with possibly multiple bulk components
- Spiked separable covariance matrices and principal components
- Superlinear convergence of conjugate gradients
- The conjugate gradient algorithm on well-conditioned Wishart matrices is almost deterministic
- The Riemann--Hilbert approach to strong asymptotics for orthogonal polynomials on [-1,1]
- The smallest eigenvalue of a large dimensional Wishart matrix
- The spectrum of kernel random matrices
- Tracy-Widom limit for the largest eigenvalue of a large class of complex sample covariance matrices
- Uniform asymptotics for polynomials orthogonal with respect to varying exponential weights and applications to universality questions in random matrix theory
- Universality for Eigenvalue Algorithms on Sample Covariance Matrices
- Universality for the Toda algorithm to compute the largest eigenvalue of a random matrix
- Universality in numerical computations with random data
Cited in
(8)- The conjugate gradient method for computing all the extremal stationary probability vectors of a stochastic matrix
- Smoothed analysis for the conjugate gradient algorithm
- On the condition number of the critically-scaled Laguerre unitary ensemble
- The conjugate gradient algorithm on well-conditioned Wishart matrices is almost deterministic
- Universality for the Conjugate Gradient and MINRES Algorithms on Sample Covariance Matrices
- GMRES, pseudospectra, and Crouzeix's conjecture for shifted and scaled Ginibre matrices
- On the asymptotics of orthogonal polynomials on multiple intervals with non-analytic weights
- High-dimensional scaling limits and fluctuations of online least-squares SGD with smooth covariance
This page was built for publication: The conjugate gradient algorithm on a general class of spiked covariance matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5022481)
