Preconvergence of the randomized extended Kaczmarz method

arXiv2105.04924MaRDI QIDQ6367358FDOQ6367358

Hanyu Li, Yanjun Zhang

Publication date: 11 May 2021

Abstract: In this paper, we analyze the convergence behavior of the randomized extended Kaczmarz (REK) method for all types of linear systems (consistent or inconsistent, overdetermined or underdetermined, full-rank or rank-deficient). The analysis shows that the larger the singular value of $A$ is, the faster the error decays in the corresponding right singular vector space, and as $kightarrowinfty$, $x_k-x_{star}$ tends to the right singular vector corresponding to the smallest singular value of $A$, where $x_k$ is the $k$th approximation of the REK method and $x_{star}$ is the minimum $el{l}_2$-norm least squares solution. These results explain the phenomenon found in the extensive numerical experiments appearing in the literature that the REK method seems to converge faster in the beginning. A simple numerical example is provided to confirm the above findings.

This page was built for publication: Preconvergence of the randomized extended Kaczmarz method

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