Preconvergence of the randomized extended Kaczmarz method
share
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 k→∞, x_k-x_⋆ tends to the right singular vector corresponding to the smallest singular value of A, where x_k is the kth approximation of the REK method and x_⋆ is the minimum ℓ_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.
READ FULL TEXT