RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



SIGMA:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


SIGMA, 2016, Volume 12, 109, 22 pages (Mi sigma1191)  

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.

Funding Agency Grant Number
National Science Foundation DMS-1411278
DMS-1303018
This work was supported in part by grants NSF-DMS-1411278 (GM) and NSF-DMS-1303018 (TT).


DOI: https://doi.org/10.3842/SIGMA.2016.109

Full text: PDF file (966 kB)
Full text: http://www.emis.de/journals/SIGMA/2016/109/
References: PDF file   HTML file

Bibliographic databases:

ArXiv: 1605.06438
MSC: 60B20; 65C50; 35Q15
Received: May 23, 2016; in final form October 31, 2016; Published online November 6, 2016
Language:

Citation: Govind Menon, Thomas Trogdon, “Smoothed Analysis for the Conjugate Gradient Algorithm”, SIGMA, 12 (2016), 109, 22 pp.

Citation in format AMSBIB
\Bibitem{MenTro16}
\by Govind~Menon, Thomas~Trogdon
\paper Smoothed Analysis for the Conjugate Gradient Algorithm
\jour SIGMA
\yr 2016
\vol 12
\papernumber 109
\totalpages 22
\mathnet{http://mi.mathnet.ru/sigma1191}
\crossref{https://doi.org/10.3842/SIGMA.2016.109}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000388502800001}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84996520939}


Linking options:
  • http://mi.mathnet.ru/eng/sigma1191
  • http://mi.mathnet.ru/eng/sigma/v12/p109

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Symmetry, Integrability and Geometry: Methods and Applications
    Number of views:
    This page:65
    Full text:12
    References:12

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019