论文标题
半随机块kaczmarz方法，具有简单的大规模线性系统的简单随机抽样
Semi-randomized block Kaczmarz methods with simple random sampling for large-scale linear systems
论文作者
论文摘要
随机块kaczmraz方法在求解大规模线性系统中起着重要作用。这种类型方法的关键点之一是如何有效选择工作行。但是，在大多数最先进的随机块kaczmarz型方法中，必须事先扫描系数矩阵的所有行以计算概率或铺路，或计算每个迭代中线性系统的残留矢量，以确定工作行。因此，我们必须在这些方法中访问数据矩阵的所有行，这对于大数据问题不利。此外，据我们所知，如何在多个线性系统的随机块kaczmarz-type方法中有效选择工作行仍然是一个开放的问题。为了解决这些问题，我们提出了半随机块kaczmarz方法，分别对具有单个右侧和多个右侧的线性系统进行简单的随机采样。在这些方法中，无需在每个步骤中扫描或铺平系数矩阵的所有行，也不需要计算线性系统的概率和残留向量。具体而言，可以同时更新具有多个右侧的大规模线性系统的所有解决方案。考虑了所提出的方法的收敛性。对现实世界和合成数据集的数值实验表明，所提出的方法优于许多用于大规模线性系统的最先进的随机Kaczmarz型方法。
Randomized block Kaczmraz method plays an important role in solving large-scale linear system. One of the key points of this type of methods is how to effectively select working rows. However, in most of the state-of-the-art randomized block Kaczmarz-type methods, one has to scan all the rows of the coefficient matrix in advance for computing probabilities or paving, or to compute the residual vector of the linear system in each iteration to determine the working rows. Thus, we have to access all the rows of the data matrix in these methods, which are unfavorable for big-data problems. Moreover, to the best of our knowledge, how to efficiently choose working rows in randomized block Kaczmarz-type methods for multiple linear systems is still an open problem. In order to deal with these problems, we propose semi-randomized block Kaczmarz methods with simple random sampling for linear systems with single and multiple right-hand sides, respectively. In these methods, there is no need to scan or pave all the rows of the coefficient matrix, nor to compute probabilities and the residual vector of the linear system in each step. Specifically, one can update all the solutions of a large-scale linear system with multiple right-hand sides simultaneously. The convergence of the proposed methods is considered. Numerical experiments on both real-world and synthetic data sets show that the proposed methods are superior to many state-of-the-art randomized Kaczmarz-type methods for large-scale linear systems.
