2021/05/11 by Yanjun Zhang, Hanyu Li, Zhang, Yanjun +1
Computer Science · Engineering · Mathematics · #FOS: Mathematics #Numerical Analysis (math.NA) #Numerical methods in inverse problems #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2105.04924
openalex publication_date 2021/05/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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→∞, xk-x⋆ tends to the right singular vector corresponding to the smallest singular value of A, where xk 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.