论文标题
一种用于求解大型线性系统的简单随机抽样的kaczmarz方法
A Kaczmarz Method with Simple Random Sampling for Solving Large Linear Systems
论文作者
论文摘要
Kaczmarz方法是一种流行的迭代方案，用于解决大规模线性系统。随机Kaczmarz方法（RK）通过以随机顺序而不是以给定的顺序使用系数矩阵的行，可以极大地提高Kaczmarz方法的收敛速率。随机Kaczmarz方法的一个明显缺点是其在系数矩阵中选择活动行或工作行的概率标准。在[{\ sc Z.Z. Bai，W。Wu}，{\ em on贪婪的随机kaczmarz方法，用于求解大型稀疏线性系统}，Siam on Scientific Computing杂志，2018，40：A592 - A606]，作者提出了一种贪婪的随机随机kaczmarz方法（GRK）。但是，当矩阵的大小较大时，这种方法可能会遭受大量计算成本，并且对于大数据问题而言，开销将非常大。这项工作的贡献如下。首先，从概率意义的角度来看，我们提出了一种部分随机的kaczmarz方法，该方法可以减少贪婪的随机kaczmarz方法中所需的计算开销。其次，根据Chebyshev的大量和Z检验定律，我们将一种简单的抽样方法应用于部分随机的Kaczmarz方法。建立了所提出方法的收敛性。第三，我们将新策略应用于脊回归问题，并提出了一种部分随机的kaczmarz方法，其中简单的随机抽样用于脊回归。数值实验表明，对于大型线性系统问题和脊回归问题，新算法比许多最先进的随机Kaczmarz方法的优越性。
The Kaczmarz method is a popular iterative scheme for solving large-scale linear systems. The randomized Kaczmarz method (RK) greatly improves the convergence rate of the Kaczmarz method, by using the rows of the coefficient matrix in random order rather than in their given order. An obvious disadvantage of the randomized Kaczmarz method is its probability criterion for selecting the active or working rows in the coefficient matrix. In [{\sc Z.Z. Bai, W. Wu}, {\em On greedy randomized Kaczmarz method for solving large sparse linear systems}, SIAM Journal on Scientific Computing, 2018, 40: A592--A606], the authors proposed a greedy randomized Kaczmarz method (GRK). However, this method may suffer from heavily computational cost when the size of the matrix is large, and the overhead will be prohibitively large for big data problems. The contribution of this work is as follows. First, from the probability significance point of view, we present a partially randomized Kaczmarz method, which can reduce the computational overhead needed in greedy randomized Kaczmarz method. Second, based on Chebyshev's law of large numbers and Z-test, we apply a simple sampling approach to the partially randomized Kaczmarz method. The convergence of the proposed method is established. Third, we apply the new strategy to the ridge regression problem, and propose a partially randomized Kaczmarz method with simple random sampling for ridge regression. Numerical experiments demonstrate the superiority of the new algorithms over many state-of-the-art randomized Kaczmarz methods for large linear systems problems and ridge regression problems.
