Symmetry, Integrability and Geometry: Methods and Applications (SIGMA)

SIGMA 12 (2016), 109, 22 pages      arXiv:1605.06438      https://doi.org/10.3842/SIGMA.2016.109
Contribution to the Special Issue on Asymptotics and Universality in Random Matrices, Random Growth Processes, Integrable Systems and Statistical Physics in honor of Percy Deift and Craig Tracy

Smoothed Analysis for the Conjugate Gradient Algorithm

Govind Menon a and Thomas Trogdon b
a) Division of Applied Mathematics, Brown University, 182 George St., Providence, RI 02912, USA
b) Department of Mathematics, University of California, Irvine, Rowland Hall, Irvine, CA, 92697-3875, USA

Received May 23, 2016, in final form October 31, 2016; Published online November 06, 2016

Abstract
The purpose of this paper is to establish bounds on the rate of convergence of the conjugate gradient algorithm when the underlying matrix is a random positive definite perturbation of a deterministic positive definite matrix. We estimate all finite moments of a natural halting time when the random perturbation is drawn from the Laguerre unitary ensemble in a critical scaling regime explored in Deift et al. (2016). These estimates are used to analyze the expected iteration count in the framework of smoothed analysis, introduced by Spielman and Teng (2001). The rigorous results are compared with numerical calculations in several cases of interest.

Key words: conjugate gradient algorithm; Wishart ensemble; Laguerre unitary ensemble; smoothed analysis.

pdf (966 kb)   tex (449 kb)

References

  1. Deift P.A., Orthogonal polynomials and random matrices: a Riemann-Hilbert approach, Courant Lecture Notes in Mathematics, Vol. 3, New York University, Courant Institute of Mathematical Sciences, New York, Amer. Math. Soc., Providence, RI, 1999.
  2. Deift P.A., Menon G., Olver S., Trogdon T., Universality in numerical computations with random data, Proc. Natl. Acad. Sci. USA 111 (2014), 14973-14978, arXiv:1407.3829.
  3. Deift P.A., Trogdon T., Universality for the Toda algorithm to compute the eigenvalues of a random matrix, arXiv:1604.07384.
  4. Deift P.A., Trogdon T., Menon G., On the condition number of the critically-scaled Laguerre unitary ensemble, Discrete Contin. Dyn. Syst. 36 (2016), 4287-4347, arXiv:1507.00750.
  5. Edelman A., Eigenvalues and condition numbers of random matrices, SIAM J. Matrix Anal. Appl. 9 (1988), 543-560.
  6. Forrester P.J., The spectrum edge of random matrix ensembles, Nuclear Phys. B 402 (1993), 709-728.
  7. Golub G.H., Van Loan C.F., Matrix computations, 4th ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2013.
  8. Greenbaum A., Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences, Linear Algebra Appl. 113 (1989), 7-63.
  9. Greenbaum A., Strakoš Z., Predicting the behavior of finite precision Lanczos and conjugate gradient computations, SIAM J. Matrix Anal. Appl. 13 (1992), 121-137.
  10. Hestenes M.R., Stiefel E., Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards 49 (1952), 409-436.
  11. Liesen J., Strakoš Z., Krylov subspace methods. Principles and analysis, Numerical Mathematics and Scientific Computation, Oxford University Press, Oxford, 2013.
  12. Marchenko V.A., Pastur L.A., Distribution of eigenvalues for some sets of random matrices, Math. USSR Sb. 1 (1967), 457-483.
  13. Olver F.W.J., Lozier D.W., Boisvert R.F., Clark C.W. (Editors), NIST handbook of mathematical functions, U.S. Department of Commerce, National Institute of Standards and Technology, Washington, DC, Cambridge University Press, Cambridge, 2010, available at \urlhttp://dlmf.nist.gov/.
  14. Pfrang C.W., Deift P., Menon G., How long does it take to compute the eigenvalues of a random symmetric matrix?, in Random Matrix Theory, Interacting Particle Systems, and Integrable Systems, Math. Sci. Res. Inst. Publ., Vol. 65, Cambridge University Press, New York, 2014, 411-442, arXiv:1203.4635.
  15. Sagun L., Trogdon T., LeCun Y., Universality in halting time and its applications in optimization, arXiv:1511.06444.
  16. Sankar A., Spielman D.A., Teng S.H., Smoothed analysis of the condition numbers and growth factors of matrices, SIAM J. Matrix Anal. Appl. 28 (2006), 446-476, cs.NA/0310022.
  17. Simon B., Trace ideals and their applications, Mathematical Surveys and Monographs, Vol. 120, 2nd ed., Amer. Math. Soc., Providence, RI, 2005.
  18. Spielman D., Teng S.H., Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time, in Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, ACM, New York, 2001, 296-305.
  19. Spielman D.A., Teng S.H., Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time, J. ACM 51 (2004), 385-463, cs.DS/0111050.
  20. Szegő G., Orthogonal polynomials, American Mathematical Society, Colloquium Publications, Vol. 23, 4th ed., Amer. Math. Soc., Providence, RI, 1975.
  21. Tracy C.A., Widom H., Level-spacing distributions and the Airy kernel, Comm. Math. Phys. 159 (1994), 151-174, hep-th/9211141.
  22. Wilkinson J.H., Error analysis of direct methods of matrix inversion, J. ACM 8 (1961), 281-330.

Previous article  Next article   Contents of Volume 12 (2016)