贪婪双子空间扩展Kaczmarz方法求解相干线性最小二乘问题

On Greedy Two-subspace Extended Kaczmarz Method for Solving Coherent Linear Least-squares Problems

摘要:

基于最大距离的采样策略，本文提出贪婪双子空间扩展Kaczmarz方法求解相干线性最小二乘问题。理论分析给出贪婪双子空间扩展Kaczmarz方法的收敛速率，并改进了双子空间随机扩展Kaczmarz方法的收敛速率上界。数值实验表明贪婪双子空间扩展Kaczmarz方法在迭代步数和计算时间上优于双子空间随机扩展Kaczmarz方法和随机双块Kaczmarz方法。

关键词:扩展Kaczmarz方法;双子空间;收敛性;线性最小二乘问题;贪婪

Abstract:

Based on an effective sampling strategy named the maximum distance rule， a greedy two-subspace extended Kaczmarz method is proposed for solving coherent linear least-squares problems. Theoretical analysis gives the convergence rate of the greedy two-subspace extended Kaczmarz method and the tighter upper bound of the convergence rate of the two-subspace randomized extended Kaczmarz method. Numerical experiments show that the greedy two-subspace extended Kaczmarz method outperforms the two-subspace randomized extended Kaczmarz method and the random double block Kaczmarz method in terms of the number of iteration steps and CPU time.

Key words:extended Kaczmarz method;two-subspace;convergence property;linear least-square problems;greedy