In this note we reconsider two known algorithms which both usually converge faster than the randomized Kaczmarz method introduced by Strohmer and Vershynin(2009), but require the additional computation of all residuals of an iteration at each step. As already indicated in the literature, e.g. arXiv:2007.02910 and arXiv:2011.14693, it is shown that the non-randomized version of the two algorithms converges at least as fast as the randomized version, while still requiring computation of all residuals. Based on that observation, a new simple random sample selection scheme has been introduced by arXiv:2011.14693 to reduce the required total of residuals. In the same light we propose an alternative random selection scheme which can easily be included as a `partially weighted selection step' into the classical randomized Kaczmarz algorithm without much ado. Numerical examples show that the randomly determined number of required residuals can be quite moderate.
翻译:在本说明中,我们重新考虑了两种已知的算法,这两种算法通常比Strohmer和Vershynin(2009年)采用的随机卡兹马尔兹法更快地趋同,但要求每步都对迭代的所有残留物进行额外的计算。正如文献中已经指出的那样,例如ArXiv:2007.02910和arXiv:2011.14693, 这表明两种算法的非随机化版本至少与随机化版本一样快,但仍然需要对所有残留物进行计算。基于这一观察,ArXiv:2011.14693采用了一个新的简单随机抽样选择方案,以减少所需的残留物总数。同样,我们提出了一种替代随机选择方案,可以很容易地作为“部分加权选择步骤”纳入经典随机化的卡兹马兹算法,而不必太多。数字实例表明随机确定的必要残留物数量可以相当适度。