一种加速的随机 Kaczmarz 算法

Oct, 2013

An Accelerated Randomized Kaczmarz Algorithm

Ji Liu, Stephen J. Wright

TL;DR提出了一种更快和更优越收敛的随机 Kaczmarz 算法及其用于支持稀疏矩阵的实现方式。研究结果表明其相对于其他算法可以在低运算成本下更有效地解决具有不同条件数的一般线性系统。

Abstract

The randomized Kaczmarz ($\RK$) algorithm is a simple but powerful approach for solving consistent linear systems $Ax=b$. This paper proposes an accelerated randomized Kaczmarz ($\ARK$) algorithm with better convergence than the standard $\RK$ algorithm on ill conditioned problems. The

randomized kaczmarz algorithm consistent linear systems ill-conditioned problems sparse implementation convergence rates

发现论文，激发创造

解决双噪线性系统的随机 Kaczmarz 算法注释

我们分析了随机 Kaczmarz 算法在含有加性和乘性噪声的线性系统中的收敛性，证明了我们的分析是稳健且适用于实际情况的，并通过全面的数值实验验证了我们的理论发现。

Aug, 2023

带噪声线性系统的随机 Kaczmarz 解算器

该研究对 Kaczmarz 算法进行了分析，证明了在有噪音的情况下，随机化方法达到了与无误差情况下相同的误差阈值，并给出了例子来展示结果在一般情况下的尖锐程度，这是解决线性方程组 Ax=b 问题的一种迭代算法。

Feb, 2009

具有指数收敛的随机 Kaczmarz 算法

介绍了 Kaczmarz 方法的随机版本来解决一致、超定的线性问题，证明了它具有期望指数收敛速度，且速度不依赖于方程的数量，甚至只需知道随机的一小部分。

Feb, 2007

随机稀疏 Kaczmarz 方法的线性收敛

提出了一种新的随机稀疏 Kaczmarz 方法并证明了它在解决线性方程组，成分分解和低秩矩阵问题方面的线性收敛性，同时数值实验表明了其优越性。

Oct, 2016

通过 Johnson-Lindenstrauss 引理加速随机 Kaczmarz 方法

本文介绍的修改版本的随机 Kaczmarz 方法，在每次迭代中从随机选择的集合中选择最佳投影，通过使用 Johnson-Lindenstrauss 维度缩减技术仅增加额外预处理时间，表现出显著的收敛加速。

Aug, 2010

解决最小二乘问题的随机扩展 Kaczmarz

我们提出了一种随机迭代算法，此算法以期望指数收敛于给定线性方程组的最小欧几里得范数最小二乘解，该算法是随机 Kaczmarz 方法的扩展，其期望运算次数正比于系统的平方条件数乘以输入矩阵的非零数目。

May, 2012

带投影的随机分块 Kaczmarz 方法求解最小二乘问题

本文介绍了基于随机投影的 Kaczmarz 方法的两个块版本，这两个版本可以期望地收敛到不一致系统的最小二乘解。通过砖石铺设 A 矩阵，可以保证这种算法的指数收敛。数值实验表明，这种方法实际上可以带来实际上的优势。

Mar, 2014

充满善意的铺路：随机分块 Kaczmarz 方法分析

本论文提出了一种采用随机控制方案的块 Kaczmarz 算法，具有预期的线性收敛率，并且在矩阵及其子矩阵的几何特性方面表示，算法的最大效力可实现为矩阵的行铺设及其子块的良好结构，并且与运算符理论文献中提供的好行铺设构造方式相结合，进而实现了对多种超定最小二乘问题的高效块 Kaczmarz 方案。

Aug, 2012

线性系统的随机迭代方法

该研究发展了一种基于随机迭代的方法来解决线性系统问题，并通过变化两个参数来恢复广泛的已知算法，并且在单个定理中证明了误差的指数收敛，并给出了预期迭代的精确公式。

Jun, 2015

随机扩展 Gauss-Seidel 和 Kaczmarz 方法的收敛性质

本文提供了关于 Kaczmarz method 和 Gauss-Seidel method 的完整理论，证明了它们在不同情形下的收敛性和推导出其变种算法的收敛性，同时证明了 Gauss-Seidel 在欠定系统情形下收敛到最小范数解。

Mar, 2015