The conjugate gradient algorithm on well-conditioned Wishart matrices is\n almost deterministic

2019/01/25 by Percy Deift, Deift, Percy, Thomas Trogdon +1 · 1 citation
Mathematics · Medicine · #60B20 #65F10 #Advanced Neuroimaging Techniques and Applications #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Numerical Analysis (math.NA) #Point processes and geometric inequalities #Probability (math.PR) #Random Matrices and Applications

paper · pdf · doi:10.48550/arxiv.1901.09007

openalex publication_date 2019/01/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that the number of iterations required to solve a random positive\ndefinite linear system with the conjugate gradient algorithm is almost\ndeterministic for large matrices. We treat the case of Wishart matrices W =\nXX^* where X is n \× m and n/m \∼ d for 0 < d < 1. Precisely, we\nprove that for most choices of error tolerance, as the matrix increases in\nsize, the probability that the iteration count deviates from an explicit\ndeterministic value tends to zero. In addition, for a fixed iteration count, we\nshow that the norm of the error vector and the norm of the residual converge\nexponentially fast in probability, converge in mean and converge almost surely.\n

Cited by

• Quadratic Objective Perturbation: Curvature-Based Differential Privacy

Related

• The conjugate gradient algorithm on a general class of spiked covariance matrices
• The gradient complexity of linear regression
• Forward and backward error bounds for a mixed precision preconditioned conjugate gradient algorithm
• Conjugate Gradient Methods with Inexact Searches
• Convergence of the Conjugate Gradient Method on Singular Systems