Estimation of spectral bounds in gradient algorithms

Pronzato, L., Zhigljavsky, Anatoly ORCID: https://orcid.org/0000-0003-0630-8279 and Bukina, A. 2012. Estimation of spectral bounds in gradient algorithms. Acta Applicandae Mathematicae 127 (1) , pp. 117-136. 10.1007/s10440-012-9794-z

Full text not available from this repository.

Abstract

We consider the solution of linear systems of equations Ax=b, with A a symmetric positive-definite matrix in ℝ n×n , through Richardson-type iterations or, equivalently, the minimization of convex quadratic functions(1/2)(Ax,x)−(b,x) with a gradient algorithm. The use of step-sizes asymptotically distributed with the arcsine distribution on the spectrum of A then yields an asymptotic rate of convergence after k<n iterations, k→∞, that coincides with that of the conjugate-gradient algorithm in the worst case. However, the spectral bounds m and M are generally unknown and thus need to be estimated to allow the construction of simple and cost-effective gradient algorithms with fast convergence. It is the purpose of this paper to analyse the properties of estimators of m and M based on moments of probability measures ν k defined on the spectrum of A and generated by the algorithm on its way towards the optimal solution. A precise analysis of the behavior of the rate of convergence of the algorithm is also given. Two situations are considered: (i) the sequence of step-sizes corresponds to i.i.d. random variables, (ii) they are generated through a dynamical system (fractional parts of the golden ratio) producing a low-discrepancy sequence. In the first case, properties of random walk can be used to prove the convergence of simple spectral bound estimators based on the first moment of ν k . The second option requires a more careful choice of spectral bounds estimators but is shown to produce much less fluctuations for the rate of convergence of the algorithm.

Item Type:	Article
Status:	Published
Schools:	Mathematics
Subjects:	Q Science > QA Mathematics
Uncontrolled Keywords:	Estimation of leading eigenvalues, Arcsine distribution, Gradient algorithms, Conjugate gradient, Fibonacci numbers
Publisher:	Springer Netherlands
ISSN:	0167-8019
Last Modified:	01 Nov 2022 09:55
URI:	https://orca.cardiff.ac.uk/id/eprint/89666

Citation Data

Cited 2 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item