论文标题
关于线性系统的无伪随机方法：统一框架和加速度
On pseudoinverse-free randomized methods for linear systems: Unified framework and acceleration
论文作者
论文摘要
我们提出了一个新的框架，用于分析和设计随机算法，用于求解各种类型的线性系统，包括一致或不一致的，全等级或排名不足。我们的方法是用四个随机采样参数配制的，该参数允许在统一框架内覆盖许多现有的随机算法的方法，包括双重随机的高斯 - seidel，随机的kaczmarz方法，随机坐标下降方法和高斯kaczmarz方法。与基于投影的块算法相比，在每次迭代时都利用用于解决最小二乘问题的伪verseverse，我们的设计是无假的。此外，新方法的灵活性还可以设计出许多新方法作为特殊情况。我们的框架中还引入了Polyak的重球动量技术，以改善该方法的收敛行为。我们证明了方法的全局线性收敛速率以及预期迭代范围的情况下的加速线性速率。最后，提供数值实验以确认我们的结果。
We present a new framework for the analysis and design of randomized algorithms for solving various types of linear systems, including consistent or inconsistent, full rank or rank-deficient. Our method is formulated with four randomized sampling parameters, which allows the method to cover many existing randomization algorithms within a unified framework, including the doubly stochastic Gauss-Seidel, randomized Kaczmarz method, randomized coordinate descent method, and Gaussian Kaczmarz method. Compared with the projection-based block algorithms where a pseudoinverse for solving a least-squares problem is utilized at each iteration, our design is pseudoinverse-free. Furthermore, the flexibility of the new approach also enables the design of a number of new methods as special cases. Polyak's heavy ball momentum technique is also introduced in our framework for improving the convergence behavior of the method. We prove the global linear convergence rates of our method as well as an accelerated linear rate for the case of the norm of expected iterates. Finally, numerical experiments are provided to confirm our results.
