The conjugate gradient algorithm on well-conditioned Wishart matrices is almost deterministic
Authors:
Percy Deift and Thomas Trogdon
Journal:
Quart. Appl. Math. 79 (2021), 125-161
MSC (2010):
Primary 65F10, 60B20
DOI:
https://doi.org/10.1090/qam/1574
Published electronically:
July 9, 2020
MathSciNet review:
4188626
Full-text PDF
Abstract |
References |
Similar Articles |
Additional Information
Abstract: We prove that the number of iterations required to solve a random positive definite linear system with the conjugate gradient algorithm is almost deterministic for large matrices. We treat the case of Wishart matrices $W = XX^*$ where $X$ is $n \times m$ and $n/m \sim d$ for $0 < d < 1$. Precisely, we prove that for most choices of error tolerance, as the matrix increases in size, the probability that the iteration count deviates from an explicit deterministic value tends to zero. In addition, for a fixed iteration count, we show that the norm of the error vector and the norm of the residual converge exponentially fast in probability, converge in mean, and converge almost surely.
References
- Mark J. Ablowitz and Athanassios S. Fokas, Complex variables: introduction and applications, 2nd ed., Cambridge Texts in Applied Mathematics, Cambridge University Press, Cambridge, 2003. MR 1989049
- Bernhard Beckermann and Arno B. J. Kuijlaars, Superlinear convergence of conjugate gradients, SIAM J. Numer. Anal. 39 (2001), no. 1, 300–329. MR 1860727, DOI https://doi.org/10.1137/S0036142999363188
- Alex Bloemendal, Antti Knowles, Horng-Tzer Yau, and Jun Yin, On the principal components of sample covariance matrices, Probab. Theory Related Fields 164 (2016), no. 1-2, 459–552. MR 3449395, DOI https://doi.org/10.1007/s00440-015-0616-x
- Z. D. Bai, B. Q. Miao, and G. M. Pan, On asymptotics of eigenvectors of large sample covariance matrix, Ann. Probab. 35 (2007), no. 4, 1532–1572. MR 2330979, DOI https://doi.org/10.1214/009117906000001079
- Zhidong Bai and Jack W. Silverstein, Spectral analysis of large dimensional random matrices, 2nd ed., Springer Series in Statistics, Springer, New York, 2010. MR 2567175
- Z. D. Bai and Y. Q. Yin, Limit of the smallest eigenvalue of a large-dimensional sample covariance matrix, Ann. Probab. 21 (1993), no. 3, 1275–1294. MR 1235416
- Ioana Dumitriu and Alan Edelman, Matrix models for beta ensembles, J. Math. Phys. 43 (2002), no. 11, 5830–5847. MR 1936554, DOI https://doi.org/10.1063/1.1507823
- P. Deift, L. C. Li, and C. Tomei, Toda flows with infinitely many variables, J. Funct. Anal. 64 (1985), no. 3, 358–402. MR 813206, DOI https://doi.org/10.1016/0022-1236%2885%2990065-5
- Percy A. Deift, Govind Menon, Sheehan Olver, and Thomas Trogdon, Universality in numerical computations with random data, Proc. Natl. Acad. Sci. USA 111 (2014), no. 42, 14973–14978. MR 3276499, DOI https://doi.org/10.1073/pnas.1413446111
- Percy A. Deift, Thomas Trogdon, and Govind Menon, On the condition number of the critically-scaled Laguerre unitary ensemble, Discrete Contin. Dyn. Syst. 36 (2016), no. 8, 4287–4347. MR 3479516, DOI https://doi.org/10.3934/dcds.2016.36.4287
- Kenneth R. Davidson and Stanislaw J. Szarek, Local operator theory, random matrices and Banach spaces, Handbook of the geometry of Banach spaces, Vol. I, North-Holland, Amsterdam, 2001, pp. 317–366. MR 1863696, DOI https://doi.org/10.1016/S1874-5849%2801%2980010-3
- Alan Edelman and Brian D. Sutton, Tails of condition number distributions, SIAM J. Matrix Anal. Appl. 27 (2005), no. 2, 547–560. MR 2179688, DOI https://doi.org/10.1137/040614256
- Gerald B. Folland, Real analysis, 2nd ed., Pure and Applied Mathematics (New York), John Wiley & Sons, Inc., New York, 1999. Modern techniques and their applications; A Wiley-Interscience Publication. MR 1681462
- P. J. Forrester, Log-gases and random matrices, London Mathematical Society Monographs Series, vol. 34, Princeton University Press, Princeton, NJ, 2010. MR 2641363
- A. Greenbaum, Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences, Linear Algebra Appl. 113 (1989), 7–63. MR 978581, DOI https://doi.org/10.1016/0024-3795%2889%2990285-1
- Herman H. Goldstine and John von Neumann, Numerical inverting of matrices of high order. II, Proc. Amer. Math. Soc. 2 (1951), 188–202. MR 41539, DOI https://doi.org/10.1090/S0002-9939-1951-0041539-X
- A. Guionnet and O. Zeitouni, Concentration of the spectral measure for large matrices, Electron. Comm. Probab. 5 (2000), 119–136. MR 1781846, DOI https://doi.org/10.1214/ECP.v5-1026
- Magnus R. Hestenes and Eduard Stiefel, Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards 49 (1952), 409–436 (1953). MR 0060307
- Arno B. J. Kuijlaars, Convergence analysis of Krylov subspace iterations with methods from potential theory, SIAM Rev. 48 (2006), no. 1, 3–40. MR 2219308, DOI https://doi.org/10.1137/S0036144504445376
- A. Lytova and L. Pastur, Central limit theorem for linear eigenvalue statistics of random matrices with independent entries, Ann. Probab. 37 (2009), no. 5, 1778–1840. MR 2561434, DOI https://doi.org/10.1214/09-AOP452
- J. C. Mason and D. C. Handscomb, Chebyshev polynomials, Chapman & Hall/CRC, Boca Raton, FL, 2003. MR 1937591
- Govind Menon and Thomas Trogdon, Smoothed analysis for the conjugate gradient algorithm, SIGMA Symmetry Integrability Geom. Methods Appl. 12 (2016), Paper No. 109, 22. MR 3568010, DOI https://doi.org/10.3842/SIGMA.2016.109
- E. Paquette and T. Trogdon, Universality for the conjugate gradient and MINRES algorithms on sample covariance matrices, arXiv:2007.00640, 1–42, 2020.
- Natesh S. Pillai and Jun Yin, Universality of covariance matrices, Ann. Appl. Probab. 24 (2014), no. 3, 935–1001. MR 3199978, DOI https://doi.org/10.1214/13-AAP939
- Daniel Spielman and Shang-Hua Teng, Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time, Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, ACM, New York, 2001, pp. 296–305. MR 2120328, DOI https://doi.org/10.1145/380752.380813
- Lloyd N. Trefethen and David Bau III, Numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1444820
- Roman Vershynin, High-dimensional probability, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 47, Cambridge University Press, Cambridge, 2018. An introduction with applications in data science; With a foreword by Sara van de Geer. MR 3837109
- J Wishart, The generalised product moment distribution in samples from a normal multivariate population, Biometrika 20A (1928), no. 1-2, 32–52.
References
- Mark J. Ablowitz and Athanassios S. Fokas, Complex variables: introduction and applications, 2nd ed., Cambridge Texts in Applied Mathematics, Cambridge University Press, Cambridge, 2003. MR 1989049
- Bernhard Beckermann and Arno B. J. Kuijlaars, Superlinear convergence of conjugate gradients, SIAM J. Numer. Anal. 39 (2001), no. 1, 300–329. MR 1860727, DOI https://doi.org/10.1137/S0036142999363188
- Alex Bloemendal, Antti Knowles, Horng-Tzer Yau, and Jun Yin, On the principal components of sample covariance matrices, Probab. Theory Related Fields 164 (2016), no. 1-2, 459–552. MR 3449395, DOI https://doi.org/10.1007/s00440-015-0616-x
- Z. D. Bai, B. Q. Miao, and G. M. Pan, On asymptotics of eigenvectors of large sample covariance matrix, Ann. Probab. 35 (2007), no. 4, 1532–1572. MR 2330979, DOI https://doi.org/10.1214/009117906000001079
- Zhidong Bai and Jack W. Silverstein, Spectral analysis of large dimensional random matrices, 2nd ed., Springer Series in Statistics, Springer, New York, 2010. MR 2567175
- Z. D. Bai and Y. Q. Yin, Limit of the smallest eigenvalue of a large-dimensional sample covariance matrix, Ann. Probab. 21 (1993), no. 3, 1275–1294. MR 1235416
- Ioana Dumitriu and Alan Edelman, Matrix models for beta ensembles, J. Math. Phys. 43 (2002), no. 11, 5830–5847. MR 1936554, DOI https://doi.org/10.1063/1.1507823
- P. Deift, L. C. Li, and C. Tomei, Toda flows with infinitely many variables, J. Funct. Anal. 64 (1985), no. 3, 358–402. MR 813206, DOI https://doi.org/10.1016/0022-1236%2885%2990065-5
- Percy A. Deift, Govind Menon, Sheehan Olver, and Thomas Trogdon, Universality in numerical computations with random data, Proc. Natl. Acad. Sci. USA 111 (2014), no. 42, 14973–14978. MR 3276499, DOI https://doi.org/10.1073/pnas.1413446111
- Percy A. Deift, Thomas Trogdon, and Govind Menon, On the condition number of the critically-scaled Laguerre unitary ensemble, Discrete Contin. Dyn. Syst. 36 (2016), no. 8, 4287–4347. MR 3479516, DOI https://doi.org/10.3934/dcds.2016.36.4287
- Kenneth R. Davidson and Stanislaw J. Szarek, Local operator theory, random matrices and Banach spaces, Handbook of the geometry of Banach spaces, Vol. I, North-Holland, Amsterdam, 2001, pp. 317–366. MR 1863696, DOI https://doi.org/10.1016/S1874-5849%2801%2980010-3
- Alan Edelman and Brian D. Sutton, Tails of condition number distributions, SIAM J. Matrix Anal. Appl. 27 (2005), no. 2, 547–560. MR 2179688, DOI https://doi.org/10.1137/040614256
- Gerald B. Folland, Real analysis: Modern techniques and their applications, 2nd ed., Pure and Applied Mathematics (New York), A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1999. MR 1681462
- P. J. Forrester, Log-gases and random matrices, London Mathematical Society Monographs Series, vol. 34, Princeton University Press, Princeton, NJ, 2010. MR 2641363
- A. Greenbaum, Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences, Linear Algebra Appl. 113 (1989), 7–63. MR 978581, DOI https://doi.org/10.1016/0024-3795%2889%2990285-1
- Herman H. Goldstine and John von Neumann, Numerical inverting of matrices of high order. II, Proc. Amer. Math. Soc. 2 (1951), 188–202. MR 41539, DOI https://doi.org/10.2307/2032484
- A. Guionnet and O. Zeitouni, Concentration of the spectral measure for large matrices, Electron. Comm. Probab. 5 (2000), 119–136. MR 1781846, DOI https://doi.org/10.1214/ECP.v5-1026
- Magnus R. Hestenes and Eduard Stiefel, Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards 49 (1952), 409–436 (1953). MR 0060307
- Arno B. J. Kuijlaars, Convergence analysis of Krylov subspace iterations with methods from potential theory, SIAM Rev. 48 (2006), no. 1, 3–40. MR 2219308, DOI https://doi.org/10.1137/S0036144504445376
- A. Lytova and L. Pastur, Central limit theorem for linear eigenvalue statistics of random matrices with independent entries, Ann. Probab. 37 (2009), no. 5, 1778–1840. MR 2561434, DOI https://doi.org/10.1214/09-AOP452
- J. C. Mason and D. C. Handscomb, Chebyshev polynomials, Chapman & Hall/CRC, Boca Raton, FL, 2003. MR 1937591
- Govind Menon and Thomas Trogdon, Smoothed analysis for the conjugate gradient algorithm, SIGMA Symmetry Integrability Geom. Methods Appl. 12 (2016), Paper No. 109, 22. MR 3568010, DOI https://doi.org/10.3842/SIGMA.2016.109
- E. Paquette and T. Trogdon, Universality for the conjugate gradient and MINRES algorithms on sample covariance matrices, arXiv:2007.00640, 1–42, 2020.
- Natesh S. Pillai and Jun Yin, Universality of covariance matrices, Ann. Appl. Probab. 24 (2014), no. 3, 935–1001. MR 3199978, DOI https://doi.org/10.1214/13-AAP939
- Daniel Spielman and Shang-Hua Teng, Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time, Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, ACM, New York, 2001, pp. 296–305. MR 2120328, DOI https://doi.org/10.1145/380752.380813
- Lloyd N. Trefethen and David Bau III, Numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1444820
- Roman Vershynin, High-dimensional probability: An introduction with applications in data science, with a foreword by Sara van de Geer, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 47, Cambridge University Press, Cambridge, 2018. MR 3837109
- J Wishart, The generalised product moment distribution in samples from a normal multivariate population, Biometrika 20A (1928), no. 1-2, 32–52.
Similar Articles
Retrieve articles in Quarterly of Applied Mathematics
with MSC (2010):
65F10,
60B20
Retrieve articles in all journals
with MSC (2010):
65F10,
60B20
Additional Information
Percy Deift
Affiliation:
New York University, Courant Institute of Mathematical Sciences, 251 Mercer St., New York, New York 10012
MR Author ID:
56085
Email:
deift@cims.nyu.edu
Thomas Trogdon
Affiliation:
Department of Applied Mathematics, University of Washington, Seattle, Washington 98195-3925
MR Author ID:
965414
ORCID:
0000-0002-6955-4154
Email:
trogdon@uw.edu
Received by editor(s):
April 27, 2020
Published electronically:
July 9, 2020
Additional Notes:
This work was supported in part by NSF DMS-1300965 (PD) and NSF DMS-1753185, DMS-1945652 (TT)
Article copyright:
© Copyright 2020
Brown University
