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

DOI10.1090/QAM/1574zbMATH Open1458.65028arXiv1901.09007OpenAlexW3042033527MaRDI QIDQ5146604FDOQ5146604

Thomas Trogdon, Percy A. Deift

Publication date: 26 January 2021

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

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}^{*}$ 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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Matrix models for beta ensembles
• Tails of Condition Number Distributions
• Spectral analysis of large dimensional random matrices
• High-Dimensional Probability
• Local operator theory, random matrices and Banach spaces.
• Methods of conjugate gradients for solving linear systems
• Title not available (Why is that?)
• Limit of the smallest eigenvalue of a large dimensional sample covariance matrix
• Title not available (Why is that?)
• Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences
• On the condition number of the critically-scaled Laguerre unitary ensemble
• Universality in numerical computations with random data
• Numerical Inverting of Matrices of High Order. II
• On asymptotics of eigenvectors of large sample covariance matrix
• Title not available (Why is that?)
• Convergence Analysis of Krylov Subspace Iterations with Methods from Potential Theory
• Central limit theorem for linear eigenvalue statistics of random matrices with independent entries
• Concentration of the spectral measure for large matrices
• Universality of covariance matrices
• Title not available (Why is that?)
• Smoothed analysis of algorithms
• Superlinear convergence of conjugate gradients
• Toda flows with infinitely many variables
• On the principal components of sample covariance matrices
• Smoothed analysis for the conjugate gradient algorithm

Cited In (6)

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

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)