Universality for the Conjugate Gradient and MINRES Algorithms on Sample Covariance Matrices. Issue 5 (1st September 2022) - Paquette, Elliot; Trogdon, Thomas
Abstract: 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. © 2022 Wiley Periodicals LLC.