Adaptively sketched Bregman projection methods for linear systems
Adaptively sketched Bregman projection methods for linear systems
复制标题
DOI：
10.1088/1361-6420/ac5f76
复制
发表时间：
2021-12
期刊：
影响因子：
2.1
通讯作者：
Ziyang Yuan;Lu Zhang;Hongxia Wang;Hui Zhang
中科院分区：
文献类型：
--
作者：
Ziyang Yuan;Lu Zhang;Hongxia Wang;Hui Zhang
草图投影算法是求解线性方程组的一种通用原型算法，它统一了随机Kaczmarz算法和随机坐标下降算法等多种随机迭代算法。然而，由于它的目的是从线性系统中找到最小范数解，因此不能包括随机稀疏Kaczmarz。这促使我们提出了一个更一般的框架，称为草图Bregman投影（SBP）方法，在其中，我们能够找到解决方案与某些结构的线性系统。为了推广自适应采样的SBP方法的概念，我们展示了如何的进步，布雷格曼距离测量，单步直接取决于一个草图的损失函数。理论上，我们提供了详细的全局收敛性结果的SBP方法与不同的自适应采样规则。最后，对稀疏Kaczmarz方法进行了一组数值模拟，验证了与其他采样规则的方法相比，采用采样Kaczmarz-Motzkin规则的方法在达到给定误差界时所需的计算量最少.
The sketch-and-project, as a general archetypal algorithm for solving linear systems, unifies a variety of randomized iterative methods such as the randomized Kaczmarz and randomized coordinate descent. However, since it aims to find a least-norm solution from a linear system, the randomized sparse Kaczmarz can not be included. This motivates us to propose a more general framework, called sketched Bregman projection (SBP) method, in which we are able to find solutions with certain structures from linear systems. To generalize the concept of adaptive sampling to the SBP method, we show how the progress, measured by Bregman distance, of single step depends directly on a sketched loss function. Theoretically, we provide detailed global convergence results for the SBP method with different adaptive sampling rules. At last, for the (sparse) Kaczmarz methods, a group of numerical simulations are tested, with which we verify that the methods utilizing sampling Kaczmarz–Motzkin rule demands the fewest computational costs to achieve a given error bound comparing to the corresponding methods with other sampling rules.