论文标题
随机扩展块kaczmarz用于求解最小二乘
Randomized extended block Kaczmarz for solving least squares
论文作者
论文摘要
最近提出了随机迭代算法来求解大规模线性系统。在本文中，我们提出了一种简单的随机扩展块kaczmarz算法，该算法将指数在均方根中呈指数收敛到给定的方程线性线性系统的唯一最小$ \ ell_2 $ -norm最小二乘解决方案。所提出的算法是不含假的，因此与基于投影的随机双块Kaczmarz算法不同，Needell，Zhao和Zouzias。我们强调，我们的方法适用于所有类型的线性系统（一致或不一致，过度确定或不确定，全等级或排名不足）。此外，我们的方法可以利用分布式计算单元上的有效实现，从而在计算时间方面取得了显着改善。给出了数值示例以显示新算法的效率。
Randomized iterative algorithms have recently been proposed to solve large-scale linear systems. In this paper, we present a simple randomized extended block Kaczmarz algorithm that exponentially converges in the mean square to the unique minimum $\ell_2$-norm least squares solution of a given linear system of equations. The proposed algorithm is pseudoinverse-free and therefore different from the projection-based randomized double block Kaczmarz algorithm of Needell, Zhao, and Zouzias. We emphasize that our method works for all types of linear systems (consistent or inconsistent, overdetermined or underdetermined, full-rank or rank-deficient). Moreover, our approach can utilize efficient implementations on distributed computing units, yielding remarkable improvements in computational time. Numerical examples are given to show the efficiency of the new algorithm.
