Smoothed Analysis for the Conjugate Gradient Algorithm

• Published in: Symmetry, Integrability and Geometry: Methods and Applications
• Date: 2016
• Main Authors: Menon, G., Trogdon, T.
• Format: Article
• Language: English
• Published: Інститут математики НАН України 2016
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/148528
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Smoothed Analysis for the Conjugate Gradient Algorithm / G. Menon, T. Trogdon // Symmetry, Integrability and Geometry: Methods and Applications. — 2016. — Т. 12. — Бібліогр.: 22 назв. — англ.

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...