论文标题
块采样Kaczmarz-Motzkin方法，用于一致的线性系统
Block sampling Kaczmarz-Motzkin methods for consistent linear systems
论文作者
论文摘要
采样Kaczmarz-Motzkin（SKM）方法是随机Kaczmarz和Motzkin方法的概括。首先，随机示例一些系数矩阵以构建集合，然后使用此组中的最大违规标准来确定约束。最后，它通过执行这个单个约束来取得进展。在本文的基础上，基于SKM方法的框架并考虑了贪婪的策略，我们为一致的线性系统提供了两个块采样Kaczmarz-Motzkin方法。具体而言，我们还首先采样系数矩阵行的子集，然后使用最大违规标准确定该集合中的索引。与SKM方法不同，在其他块方法中，我们设计了不同的贪婪策略来构建索引集。然后，新方法通过同时执行相应的多个约束来取得进展。理论分析表明，这些块方法至少与SKM方法一样快地收敛，而数值实验表明，就相同的精度而言，我们的方法在迭代次数和计算时间方面优于SKM方法。
The sampling Kaczmarz-Motzkin (SKM) method is a generalization of the randomized Kaczmarz and Motzkin methods. It first samples some rows of coefficient matrix randomly to build a set and then makes use of the maximum violation criterion within this set to determine a constraint. Finally, it makes progress by enforcing this single constraint. In this paper, on the basis of the framework of the SKM method and considering the greedy strategies, we present two block sampling Kaczmarz-Motzkin methods for consistent linear systems. Specifically, we also first sample a subset of rows of coefficient matrix and then determine an index in this set using the maximum violation criterion. Unlike the SKM method, in the rest of the block methods, we devise different greedy strategies to build index sets. Then, the new methods make progress by enforcing the corresponding multiple constraints simultaneously. Theoretical analyses demonstrate that these block methods converge at least as quickly as the SKM method, and numerical experiments show that, for the same accuracy, our methods outperform the SKM method in terms of the number of iterations and computing time.
