解决最小二乘问题的随机扩展 Kaczmarz
本文介绍了基于随机投影的 Kaczmarz 方法的两个块版本,这两个版本可以期望地收敛到不一致系统的最小二乘解。通过砖石铺设 A 矩阵,可以保证这种算法的指数收敛。数值实验表明,这种方法实际上可以带来实际上的优势。
Mar, 2014
介绍了 Kaczmarz 方法的随机版本来解决一致、超定的线性问题,证明了它具有期望指数收敛速度,且速度不依赖于方程的数量,甚至只需知道随机的一小部分。
Feb, 2007
该研究对 Kaczmarz 算法进行了分析,证明了在有噪音的情况下,随机化方法达到了与无误差情况下相同的误差阈值,并给出了例子来展示结果在一般情况下的尖锐程度,这是解决线性方程组 Ax=b 问题的一种迭代算法。
Feb, 2009
提出了一种新的随机稀疏 Kaczmarz 方法并证明了它在解决线性方程组,成分分解和低秩矩阵问题方面的线性收敛性,同时数值实验表明了其优越性。
Oct, 2016
本文介绍的修改版本的随机 Kaczmarz 方法,在每次迭代中从随机选择的集合中选择最佳投影,通过使用 Johnson-Lindenstrauss 维度缩减技术仅增加额外预处理时间,表现出显著的收敛加速。
Aug, 2010
该研究发展了一种基于随机迭代的方法来解决线性系统问题,并通过变化两个参数来恢复广泛的已知算法,并且在单个定理中证明了误差的指数收敛,并给出了预期迭代的精确公式。
Jun, 2015
本论文提出了一种采用随机控制方案的块 Kaczmarz 算法,具有预期的线性收敛率,并且在矩阵及其子矩阵的几何特性方面表示,算法的最大效力可实现为矩阵的行铺设及其子块的良好结构,并且与运算符理论文献中提供的好行铺设构造方式相结合,进而实现了对多种超定最小二乘问题的高效块 Kaczmarz 方案。
Aug, 2012
提出了一种更快和更优越收敛的随机 Kaczmarz 算法及其用于支持稀疏矩阵的实现方式。研究结果表明其相对于其他算法可以在低运算成本下更有效地解决具有不同条件数的一般线性系统。
Oct, 2013
本文提供了关于 Kaczmarz method 和 Gauss-Seidel method 的完整理论,证明了它们在不同情形下的收敛性和推导出其变种算法的收敛性,同时证明了 Gauss-Seidel 在欠定系统情形下收敛到最小范数解。
Mar, 2015
我们分析了随机 Kaczmarz 算法在含有加性和乘性噪声的线性系统中的收敛性,证明了我们的分析是稳健且适用于实际情况的,并通过全面的数值实验验证了我们的理论发现。
Aug, 2023