Geodesic
Smoothed Analysis for the Conjugate Gradient Algorithm
Symmetry, integrability and geometry: methods and applications, Tome 12 (2016) Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: conjugate gradient algorithm; Wishart ensemble; Laguerre unitary ensemble; smoothed analysis. 
@article{SIGMA_2016_12_a108,
     author = {Govind Menon and Thomas Trogdon},
     title = {Smoothed {Analysis} for the {Conjugate} {Gradient} {Algorithm}},
     journal = {Symmetry, integrability and geometry: methods and applications},
     year = {2016},
     volume = {12},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SIGMA_2016_12_a108/}
}
TY  - JOUR
AU  - Govind Menon
AU  - Thomas Trogdon
TI  - Smoothed Analysis for the Conjugate Gradient Algorithm
JO  - Symmetry, integrability and geometry: methods and applications
PY  - 2016
VL  - 12
UR  - http://geodesic.mathdoc.fr/item/SIGMA_2016_12_a108/
LA  - en
ID  - SIGMA_2016_12_a108
ER  - 
%0 Journal Article
%A Govind Menon
%A Thomas Trogdon
%T Smoothed Analysis for the Conjugate Gradient Algorithm
%J Symmetry, integrability and geometry: methods and applications
%D 2016
%V 12
%U http://geodesic.mathdoc.fr/item/SIGMA_2016_12_a108/
%G en
%F SIGMA_2016_12_a108
Govind Menon; Thomas Trogdon. Smoothed Analysis for the Conjugate Gradient Algorithm. Symmetry, integrability and geometry: methods and applications, Tome 12 (2016). http://geodesic.mathdoc.fr/item/SIGMA_2016_12_a108/

[1] Deift P. A., Orthogonal polynomials and random matrices: a Riemann–Hilbert approach, Courant Lecture Notes in Mathematics, 3, New York University, Courant Institute of Mathematical Sciences, New York; Amer. Math. Soc., 1999 | DOI | MR

[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 | DOI | MR

[3] Deift P. A., Trogdon T., Universality for the {T}oda 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 | DOI | MR | Zbl

[5] Edelman A., “Eigenvalues and condition numbers of random matrices”, SIAM J. Matrix Anal. Appl., 9 (1988), 543–560 | DOI | MR | Zbl

[6] Forrester P. J., “The spectrum edge of random matrix ensembles”, Nuclear Phys. B, 402 (1993), 709–728 | DOI | MR | Zbl

[7] Golub G. H., Van Loan C. F., Matrix computations, Johns Hopkins Studies in the Mathematical Sciences, 4th ed., Johns Hopkins University Press, Baltimore, MD, 2013 | MR | Zbl

[8] Greenbaum A., “Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences”, Linear Algebra Appl., 113 (1989), 7–63 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[10] Hestenes M. R., Stiefel E., “Methods of conjugate gradients for solving linear systems”, J. Research Nat. Bur. Standards, 49 (1952), 409–436 | DOI | MR | Zbl

[11] Liesen J., Strakoš Z., Krylov subspace methods. Principles and analysis, Numerical Mathematics and Scientific Computation, Oxford University Press, Oxford, 2013 | MR | Zbl

[12] Marchenko V. A., Pastur L. A., “Distribution of eigenvalues for some sets of random matrices”, Math. USSR Sb., 1 (1967), 457–483 | DOI

[13] Olver F. W. J., Lozier D. W., Boisvert R. F., Clark C. W. (eds.), NIST handbook of mathematical functions, U.S. Department of Commerce, National Institute of Standards and Technology, Washington, DC; Cambridge University Press, Cambridge, 2010 http://dlmf.nist.gov/ | MR

[14] Pfrang C. W., Deift P., Menon G., How long does it take to compute the eigenvalues of a random symmetric matrix?, Random Matrix Theory, Interacting Particle Systems, and Integrable Systems, Math. Sci. Res. Inst. Publ., 65, Cambridge University Press, New York, 2014, 411–442, arXiv: 1203.4635 | MR | Zbl

[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, arXiv: cs.NA/0310022 | DOI | MR | Zbl

[17] Simon B., Trace ideals and their applications, Mathematical Surveys and Monographs, 120, 2nd ed., Amer. Math. Soc., Providence, RI, 2005 | MR | Zbl

[18] Spielman D., Teng S. H., “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, 296–305 | DOI | MR | Zbl

[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, arXiv: cs.DS/0111050 | DOI | MR | Zbl

[20] Szeg{ő} G., Orthogonal polynomials, American Mathematical Society, Colloquium Publications, 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, arXiv: hep-th/9211141 | DOI | MR | Zbl

[22] Wilkinson J. H., “Error analysis of direct methods of matrix inversion”, J. ACM, 8 (1961), 281–330 | DOI | MR | Zbl