Skip to Main Content
Quarterly of Applied Mathematics

Quarterly of Applied Mathematics

Online ISSN 1552-4485; Print ISSN 0033-569X



The conjugate gradient algorithm on a general class of spiked covariance matrices

Authors: Xiucai Ding and Thomas Trogdon
Journal: Quart. Appl. Math. 80 (2022), 99-155
MSC (2020): Primary 65F10, 60B20
Published electronically: November 19, 2021
MathSciNet review: 4360552
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We consider the conjugate gradient algorithm applied to a general class of spiked sample covariance matrices. The main result of the paper is that the norms of the error and residual vectors at any finite step concentrate on deterministic values determined by orthogonal polynomials with respect to a deformed Marchenko–Pastur law. The first-order limits and fluctuations are shown to be universal. Additionally, for the case where the bulk eigenvalues lie in a single interval we show a stronger universality result in that the asymptotic rate of convergence of the conjugate gradient algorithm only depends on the support of the bulk, provided the spikes are well-separated from the bulk. In particular, this shows that the classical condition number bound for the conjugate gradient algorithm is pessimistic for spiked matrices.

References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Quarterly of Applied Mathematics with MSC (2020): 65F10, 60B20

Retrieve articles in all journals with MSC (2020): 65F10, 60B20

Additional Information

Xiucai Ding
Affiliation: Department of Statistics, University of California Davis, Davis, CA 95616
MR Author ID: 1273109

Thomas Trogdon
Affiliation: Department of Applied Mathematics, University of Washington, Seattle, WA 98195-3925
MR Author ID: 965414
ORCID: 0000-0002-6955-4154

Keywords: Sample covariance matrices, conjugate gradient
Received by editor(s): October 13, 2021
Published electronically: November 19, 2021
Additional Notes: The authors gratefully acknowledge support from the US National Science Foundation under grant NSF-DMS-1945652 (TT). Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the funding sources.
Article copyright: © Copyright 2021 Brown University