دورية أكاديمية
Estimation of spectral bounds in gradient algorithms
| العنوان: | Estimation of spectral bounds in gradient algorithms |
|---|---|
| المؤلفون: | Pronzato, Luc, Zhigljavsky, Anatoly, A., Bukina, Elena |
| المساهمون: | Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Equipe SYSTEMES, Signal, Images et Systèmes (Laboratoire I3S - SIS), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA), School of Mathematics Cardiff, Cardiff University, The work of E. Bukina was partially supported by the EU through a Marie-Curie Fellowship (EST-SIGNAL program: http://est-signal.i3s.unice.frTest) under the contract Nb. MEST-CT-2005-021175. |
| المصدر: | ISSN: 0167-8019. |
| بيانات النشر: | HAL CCSD Springer Verlag |
| سنة النشر: | 2013 |
| المجموعة: | HAL Université Côte d'Azur |
| مصطلحات موضوعية: | estimation of leading eigenvalues, arcsine distribution, gradient algorithms, conjugate gradient, Fibonacci numbers, MSC 65F10, 65F15, [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], [STAT.TH]Statistics [stat]/Statistics Theory [stat.TH] |
| الوصف: | International audience ; We consider the solution of linear systems of equations Ax = b, with A a symmetric positive-definite matrix in R nxn, 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 -> infinity, 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 nuk 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 nuk. 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. |
| نوع الوثيقة: | article in journal/newspaper |
| اللغة: | English |
| العلاقة: | hal-01001685; https://hal.science/hal-01001685Test; https://hal.science/hal-01001685/documentTest; https://hal.science/hal-01001685/file/AAM_PZB_final.pdfTest |
| DOI: | 10.1007/s10440-012-9794-z |
| الإتاحة: | https://doi.org/10.1007/s10440-012-9794-zTest https://hal.science/hal-01001685Test https://hal.science/hal-01001685/documentTest https://hal.science/hal-01001685/file/AAM_PZB_final.pdfTest |
| حقوق: | info:eu-repo/semantics/OpenAccess |
| رقم الانضمام: | edsbas.722A36B2 |
| قاعدة البيانات: | BASE |
| DOI: | 10.1007/s10440-012-9794-z |
|---|