Premium
Selectable Set Randomized Kaczmarz
Author(s) -
Yaniv Yotam,
Moorman Jacob D.,
Swartworth William,
Tu Thomas,
Landis Daji,
Needell Deanna
Publication year - 2023
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.2458
Subject(s) - mathematics , convergence (economics) , set (abstract data type) , mathematical optimization , selectable marker , algorithm , computer science , theoretical computer science , transformation (genetics) , biochemistry , chemistry , economics , gene , programming language , economic growth
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.