TY - JOUR

T1 - The Conjugate Gradient Algorithm on Well-Conditioned Wishart Matrices is Almost Deterministic

AU - Deift, Percy

AU - Trogdon, Thomas

N1 - Funding Information:
Received April 27, 2020. 2010 Mathematics Subject Classification. Primary 65F10, 60B20. This work was supported in part by NSF DMS-1300965 (PD) and NSF DMS-1753185, DMS-1945652 (TT). Email address: [email protected] Email address: [email protected]

PY - 2020/7/9

Y1 - 2020/7/9

N2 - 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 = XX* where X is n x m and n/m ̰ d for0 < 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.

AB - 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 = XX* where X is n x m and n/m ̰ d for0 < 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.

UR - http://www.scopus.com/inward/record.url?scp=85098103560&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85098103560&partnerID=8YFLogxK

U2 - 10.1090/QAM/1574

DO - 10.1090/QAM/1574

M3 - Article

AN - SCOPUS:85098103560

SN - 0033-569X

VL - 79

SP - 125

EP - 161

JO - Quarterly of Applied Mathematics

JF - Quarterly of Applied Mathematics

IS - 1

ER -