Selectable Set Randomized Kaczmarz
Selectable Set Randomized Kaczmarz
复制标题
DOI：
10.1002/nla.2458
复制
发表时间：
2021-10
影响因子：
4.3
通讯作者：
Yotam Yaniv;Jacob D. Moorman;W. Swartworth;Thomas K. Tu;Daji Landis;D. Needell
中科院分区：
文献类型：
--
作者：
Yotam Yaniv;Jacob D. Moorman;W. Swartworth;Thomas K. Tu;Daji Landis;D. Needell
随机 Kaczmarz 方法 (RK) 是一种用于求解线性系统的随机迭代方法，由于其速度快且内存需求低，最近越来越受欢迎。可选集随机 Kaczmarz 是 RK 的一种变体，它利用有关 Kaczmarz 迭代的现有信息来识别自适应“可选集”，从而产生改进的收敛保证。在本文中，我们提出了可选择集合方法的一般视角，并证明了该框架的收敛结果。此外，我们定义了两种特定的可选集采样策略，它们与 RK 的其他变体具有竞争性收敛保证。一种可选择的集合采样策略利用有关先前迭代的信息，而另一种则通过格拉米亚矩阵利用问题的正交结构。我们用数值实验来补充我们的理论结果，将我们提出的规则与文献中现有的规则进行比较。
The Randomized Kaczmarz method (RK) is a stochastic iterative method for solving linear systems that has recently grown in popularity due to its speed and low memory requirement. Selectable Set Randomized Kaczmarz is a variant of RK that leverages existing information about the Kaczmarz iterate to identify an adaptive “selectable set” and thus yields an improved convergence guarantee. In this article, we propose a general perspective for selectable set approaches and prove a convergence result for that framework. In addition, we define two specific selectable set sampling strategies that have competitive convergence guarantees to those of other variants of RK. One selectable set sampling strategy leverages information about the previous iterate, while the other leverages the orthogonality structure of the problem via the Gramian matrix. We complement our theoretical results with numerical experiments that compare our proposed rules with those existing in the literature.