2025/12/10 by Dong, Zeyu, Xiao, Aqin, Yin, Guojian +1
#65F10 #65F22 #FOS: Mathematics #Numerical Analysis (math.NA)
paper · doi:10.48550/arxiv.2512.09825
Randomized Kaczmarz-type methods are widely used for their simplicity and efficiency in solving large-scale linear systems and optimization problems. However, their applicability is limited when dealing with inconsistent systems or incorporating structural information such as sparsity. In this work, we propose a relaxed randomized averaging block extended Bregman-Kaczmarz (rRABEBK) method for solving a broad class of combined optimization problems. The proposed method integrates an averaging block strategy with two relaxation parameters to accelerate convergence and enhance numerical stability. We establish a rigorous convergence theory showing that rRABEBK achieves linear convergence in expectation, with explicit constants that quantify the effect of the relaxation mechanism, and a provably faster rate than the classical randomized extended Bregman-Kaczmarz method. Our method can be readily adapted to sparse least-squares problems and extended to both consistent and inconsistent systems without modification. Complementary numerical experiments corroborate the theoretical findings and demonstrate that rRABEBK significantly outperforms the existing Kaczmarz-type algorithms in terms of both iteration complexity and computational efficiency, highlighting both its practical and theoretical advantages.