Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

Estimation of spectral bounds in gradient algorithms

Pronzato, L., Zhigljavsky, Anatoly ORCID: 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.


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

Citation Data

Cited 1 time in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item Edit Item