论文标题
贪婪的块高斯 - 西德尔方法，用于解决大型线性最小二乘问题
Greedy Block Gauss-Seidel Methods for Solving Large Linear Least Squares Problem
论文作者
论文摘要
首先，采用贪婪的策略来构建控制索引的控制索引集，然后在每次迭代中选择相应的列subbatrix，我们提出了一种贪婪的块高斯 - 塞德尔（GBGS）方法来求解大型线性最小二乘问题。理论分析表明，GBGS方法的收敛因子可能比最近在文献中提出的贪婪随机坐标下降（GRCD）方法小得多。基于GBGS方法，我们进一步提出了一种无伪贪婪的贪婪块高斯 - 塞德尔方法，该方法不需要在每种迭代中计算圆柱子质体的Moore-Penrose Pseudoinverse，更多地，因此可以实现更大的加速度。此外，此方法也可以用于分布式实现。数值实验表明，就相同的精度而言，我们的方法在迭代编号和计算时间方面远远超过了GRCD方法。
With a greedy strategy to construct control index set of coordinates firstly and then choosing the corresponding column submatrix in each iteration, we present a greedy block Gauss-Seidel (GBGS) method for solving large linear least squares problem. Theoretical analysis demonstrates that the convergence factor of the GBGS method can be much smaller than that of the greedy randomized coordinate descent (GRCD) method proposed recently in the literature. On the basis of the GBGS method, we further present a pseudoinverse-free greedy block Gauss-Seidel method, which doesn't need to calculate the Moore-Penrose pseudoinverse of the column submatrix in each iteration any more and hence can be achieved greater acceleration. Moreover, this method can also be used for distributed implementations. Numerical experiments show that, for the same accuracy, our methods can far outperform the GRCD method in terms of the iteration number and computing time.
