Universality for the conjugate gradient and MINRES algorithms on sample covariance matrices

07/01/2020
by   Elliot Paquette, et al.
0

We present a probabilistic analysis of two Krylov subspace methods for solving linear systems. We prove a central limit theorem for norms of the residual vectors that are produced by the conjugate gradient and MINRES algorithms when applied to a wide class of sample covariance matrices satisfying some standard moment conditions. The proof involves establishing a four moment theorem for the so-called spectral measure, implying, in particular, universality for the matrix produced by the Lanczos iteration. The central limit theorem then implies an almost-deterministic iteration count for the iterative methods in question.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset