|
This article is cited in 2 scientific papers (total in 2 papers)
Smoothed Analysis for the Conjugate Gradient Algorithm
Govind Menona, Thomas Trogdonb 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
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.
Keywords:
conjugate gradient algorithm; Wishart ensemble; Laguerre unitary ensemble; smoothed analysis.
Received: May 23, 2016; in final form October 31, 2016; Published online November 6, 2016
Citation:
Govind Menon, Thomas Trogdon, “Smoothed Analysis for the Conjugate Gradient Algorithm”, SIGMA, 12 (2016), 109, 22 pp.
Linking options:
https://www.mathnet.ru/eng/sigma1191 https://www.mathnet.ru/eng/sigma/v12/p109
|
Statistics & downloads: |
Abstract page: | 123 | Full-text PDF : | 23 | References: | 16 |
|