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

01/25/2019
by   Percy Deift, et al.
0

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. 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, we show that the norm of the error vector and the norm of the residual converge exponentially fast in probability, converge in mean, converge almost surely and, after centering and rescaling, converge in distribution.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset