The conjugate gradient algorithm on well-conditioned Wishart matrices is almost deterministic

DOI10.1090/QAM/1574MaRDI QIDQ5146604zbMATH OpenOpenAlexFDO

Authors Thomas Trogdon, Percy A. Deift

Publication date 26 January 2021

Published in Quarterly of Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

convergence analysisconjugate gradient methodWishart matricesrandom positive definite linear system

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20) Iterative numerical methods for linear systems (65F10)

Abstract: We prove that the number of iterations required to solve a random positive definite linear system with the conjugate gradient algorithm is almost deterministic for large matrices. We treat the case of Wishart matrices $W=X{X}^{\ast }$ where $X$ is $nimesm$ and $n/msimd$ for $0<d<1$. Precisely, we prove that for most choices of error tolerance, as the matrix increases in size, the probability that the iteration count deviates from an explicit deterministic value tends to zero. In addition, for a fixed iteration count, we show that the norm of the error vector and the norm of the residual converge exponentially fast in probability, converge in mean and converge almost surely.

Recommendations

• Smoothed analysis for the conjugate gradient algorithm
• The conjugate gradient algorithm on a general class of spiked covariance matrices
• On the real convergence rate of the conjugate gradient method
• On the condition number of the critically-scaled Laguerre unitary ensemble
• On prescribing the convergence behavior of the conjugate gradient algorithm

Cites work

• scientific article; zbMATH DE number 1324223 (Why is no real title available?)
• scientific article; zbMATH DE number 1012640 (Why is no real title available?)
• scientific article; zbMATH DE number 1966261 (Why is no real title available?)
• scientific article; zbMATH DE number 1862742 (Why is no real title available?)
• Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences
• Central limit theorem for linear eigenvalue statistics of random matrices with independent entries
• Concentration of the spectral measure for large matrices
• Convergence Analysis of Krylov Subspace Iterations with Methods from Potential Theory
• High-dimensional probability. An introduction with applications in data science
• Limit of the smallest eigenvalue of a large dimensional sample covariance matrix
• Local operator theory, random matrices and Banach spaces.
• Log-gases and random matrices.
• Matrix models for beta ensembles
• Methods of conjugate gradients for solving linear systems
• 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 principal components of sample covariance matrices
• Smoothed analysis for the conjugate gradient algorithm
• Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time
• Spectral analysis of large dimensional random matrices
• Superlinear convergence of conjugate gradients
• Tails of Condition Number Distributions
• Toda flows with infinitely many variables
• Universality in numerical computations with random data
• Universality of covariance matrices

Cited in

(8)

• GMRES, pseudospectra, and Crouzeix's conjecture for shifted and scaled Ginibre matrices
• The conjugate gradient method for computing all the extremal stationary probability vectors of a stochastic matrix
• The conjugate gradient algorithm on a general class of spiked covariance matrices
• Stability of the Lanczos algorithm on matrices with regular spectral distributions
• Smoothed analysis for the conjugate gradient algorithm
• Universality for the Conjugate Gradient and MINRES Algorithms on Sample Covariance Matrices
• Halting time is predictable for large models: a universality property and average-case analysis
• On the condition number of the critically-scaled Laguerre unitary ensemble

Describes a project that uses

Uses Software

• numericaluniversality

This page was built for publication: The conjugate gradient algorithm on well-conditioned Wishart matrices is almost deterministic

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