Preasymptotic convergence of randomized Kaczmarz method. (English) Zbl 1382.65087

Jiao, Yuling; Jin, Bangti; Lu, Xiliang

Inverse Probl. 33, No. 12, Article ID 125012, 21 p. (2017).

The paper proposes a study of a the preasymptotic convergence behavior of randomized Kaczmarz method. It is based on the analysis of the evolution of the low- and high-frequency errors during the randomized Kaczmarz iteration, where the frequency is divided according to the right singular vectors of the system matrix. The obtained results indicate that during the initial iterations, the low-frequency error decays must be faster than the high-frequency one. Therefore, because the inverse solution is often smooth in the sense that it consists mostly of low-frequency components, this explains the good convergence behavior of the randomized Kaczmarz iteration for some classes of problems.

Reviewer: Constantin Popa (Constanţa)

MSC:

65F10

Iterative numerical methods for linear systems

Keywords:

randomized Kaczmarz method; preasymptotic convergence; smoothness; error estimates; variance reduction