求解带扰动的线性方程组的贪婪随机Kaczmarz方法

Greedy Randomized Kaczmarz Method for Solving Noisy Linear Systems

摘要:

当相容的线性代数方程组的右端向量发生扰动时，给出了由贪婪随机Kaczmarz方法所产生的迭代解与原线性代数方程组的最小范数解之间的期望误差的上界，并说明了随着迭代步数的增长，该期望解误差以线性速率下降至一个给定阈值。数值实验表明，该阈值能够很好地估计贪婪随机Kaczmarz方法的迭代解误差所能达到的最小值。

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.