Smoothed analysis for the conjugate gradient algorithm

DOI10.3842/SIGMA.2016.109MaRDI QIDQ2520124zbMATH OpenOpenAlexFDO

Authors Thomas Trogdon, Govind Menon

Publication date 13 December 2016

Published in SIGMA. Symmetry, Integrability and Geometry: Methods and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.06438

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

conjugate gradient algorithmLaguerre unitary ensembleWishart ensemblesmoothed analysis

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Iterative numerical methods for linear systems (65F10) Riemann-Hilbert problems in context of PDEs (35Q15)

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.

Recommendations

• The conjugate gradient algorithm on well-conditioned Wishart matrices is almost deterministic
• The conjugate gradient algorithm on a general class of spiked covariance matrices
• Properties of generalized conjugate gradient methods
• On the real convergence rate of the conjugate gradient method
• Smoothed analysis of condition numbers

Cites work

• scientific article; zbMATH DE number 3477793 (Why is no real title available?)
• scientific article; zbMATH DE number 6159604 (Why is no real title available?)
• scientific article; zbMATH DE number 2212219 (Why is no real title available?)
• Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences
• DISTRIBUTION OF EIGENVALUES FOR SOME SETS OF RANDOM MATRICES
• Eigenvalues and Condition Numbers of Random Matrices
• Error Analysis of Direct Methods of Matrix Inversion
• How long does it take to compute the eigenvalues of a random symmetric matrix?
• Krylov subspace methods. Principles and analysis.
• Level-spacing distributions and the Airy kernel
• Methods of conjugate gradients for solving linear systems
• NIST handbook of mathematical functions
• On the condition number of the critically-scaled Laguerre unitary ensemble
• Predicting the Behavior of Finite Precision Lanczos and Conjugate Gradient Computations
• Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
• Smoothed analysis of algorithms
• Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time
• The spectrum edge of random matrix ensembles.
• Universal halting times in optimization and machine learning
• Universality for the Toda algorithm to compute the largest eigenvalue of a random matrix
• Universality in numerical computations with random data

Cited in

(6)

• Universality for the Conjugate Gradient and MINRES Algorithms on Sample Covariance Matrices
• Smoothed Analysis of Moore–Penrose Inversion
• The conjugate gradient algorithm on a general class of spiked covariance matrices
• The conjugate gradient algorithm on well-conditioned Wishart matrices is almost deterministic
• Universality for Eigenvalue Algorithms on Sample Covariance Matrices
• Halting time is predictable for large models: a universality property and average-case analysis

Describes a project that uses

Uses Software

• numericaluniversality

This page was built for publication: Smoothed analysis for the conjugate gradient algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2520124)