Greedy Randomized Kaczmarz Method for Solving Noisy Linear Systems

Abstract:

When the right-hand side vector of the consistent system of linear equations is disturbed by noise， we give an upper bound for the error in expectation between the iteration vector generated by the greedy randomized Kaczmarz method and the least-norm solution of the noise-free system of linear equations， and illuminate that， as the iteration step increases， this solution error in expectation decreases to a given threshold with a linear rate. Numerical experiments show that this threshold can give a good estimate of minimum that the iterative solution error of the greedy randomized Kaczmarz method can reach.