Universality for the Conjugate Gradient and MINRES Algorithms on Sample Covariance Matrices |
| |
Authors: | Elliot Paquette Thomas Trogdon |
| |
Institution: | 1. McGill University, Department of Mathematics and Statistics, 805 Rue Sherbrooke O, Montréal, QC, H3A 2K6 Canada;2. University of Washington, Department of Applied Mathematics, Seattle, WA, 98195-3925 USA |
| |
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. |
| |
Keywords: | Sample covariance matrices conjugate gradient MINRES Wishart distribution |
|
|