Universality for the Conjugate Gradient and MINRES Algorithms on Sample Covariance Matrices. Issue 5 (1st September 2022)

• Record Type: Journal Article
• Authors: Paquette, Elliot; Trogdon, Thomas
• Is Part Of: Communications on pure and applied mathematics. Volume 76:Issue 5(2023)
• Page Start: 1085
• Page End: 1136
• Publication Date: 2022-09-01
• Subjects: Sample covariance matrices -- conjugate gradient -- MINRES -- Wishart distribution; Mathematics -- Periodicals; Mechanics -- Periodicals; Mathématiques -- Périodiques; Mécanique -- Périodiques; 510.5
• DOI: 10.1002/cpa.22081
• Languages: English
• ISSNs: 0010-3640

Abstract

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.