Smoothed Analysis for the Conjugate Gradient Algorithm
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...
Збережено в:
| Опубліковано в: : | Symmetry, Integrability and Geometry: Methods and Applications |
|---|---|
| Дата: | 2016 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Англійська |
| Опубліковано: |
Інститут математики НАН України
2016
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/148528 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Smoothed Analysis for the Conjugate Gradient Algorithm / G. Menon, T. Trogdon // Symmetry, Integrability and Geometry: Methods and Applications. — 2016. — Т. 12. — Бібліогр.: 22 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862593789078536192 |
|---|---|
| author | Menon, G. Trogdon, T. |
| author_facet | Menon, G. Trogdon, T. |
| citation_txt | Smoothed Analysis for the Conjugate Gradient Algorithm / G. Menon, T. Trogdon // Symmetry, Integrability and Geometry: Methods and Applications. — 2016. — Т. 12. — Бібліогр.: 22 назв. — англ. |
| collection | DSpace DC |
| container_title | Symmetry, Integrability and Geometry: Methods and Applications |
| description | 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.
|
| first_indexed | 2025-11-27T10:33:35Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-148528 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1815-0659 |
| language | English |
| last_indexed | 2025-11-27T10:33:35Z |
| publishDate | 2016 |
| publisher | Інститут математики НАН України |
| record_format | dspace |
| spelling | Menon, G. Trogdon, T. 2019-02-18T14:45:41Z 2019-02-18T14:45:41Z 2016 Smoothed Analysis for the Conjugate Gradient Algorithm / G. Menon, T. Trogdon // Symmetry, Integrability and Geometry: Methods and Applications. — 2016. — Т. 12. — Бібліогр.: 22 назв. — англ. 1815-0659 2010 Mathematics Subject Classification: 60B20; 65C50; 35Q15 DOI:10.3842/SIGMA.2016.109 https://nasplib.isofts.kiev.ua/handle/123456789/148528 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. This paper is a 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.
 The full collection is available at http://www.emis.de/journals/SIGMA/Deift-Tracy.html.
 This work was supported in part by grants NSF-DMS-1411278 (GM) and NSF-DMS-1303018
 (TT). The authors thank Anne Greenbaum and Zdenˇek Strakoˇs for useful conversations, Folkmar
 Bornemann for suggesting that we consider the framework of smoothed analysis and the
 anonymous referees for suggesting additional numerical experiments. en Інститут математики НАН України Symmetry, Integrability and Geometry: Methods and Applications Smoothed Analysis for the Conjugate Gradient Algorithm Article published earlier |
| spellingShingle | Smoothed Analysis for the Conjugate Gradient Algorithm Menon, G. Trogdon, T. |
| title | Smoothed Analysis for the Conjugate Gradient Algorithm |
| title_full | Smoothed Analysis for the Conjugate Gradient Algorithm |
| title_fullStr | Smoothed Analysis for the Conjugate Gradient Algorithm |
| title_full_unstemmed | Smoothed Analysis for the Conjugate Gradient Algorithm |
| title_short | Smoothed Analysis for the Conjugate Gradient Algorithm |
| title_sort | smoothed analysis for the conjugate gradient algorithm |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/148528 |
| work_keys_str_mv | AT menong smoothedanalysisfortheconjugategradientalgorithm AT trogdont smoothedanalysisfortheconjugategradientalgorithm |