摘要
随机Kaczmarz方法是通过反复将迭代向量投影到随机选取的方程上来收敛的线性系统求解器家族。虽然在高度超定最小二乘等场景中有效，但传统认为Kaczmarz方法次于Krylov子空间方法，因为后者能利用输入矩阵奇异值分布中的异常值在病态系统上实现快速收敛。
本文提出Kaczmarz++——一种加速随机块Kaczmarz算法，通过利用输入矩阵中的异常奇异值实现类Krylov的快速收敛。研究证明，对于超定和欠定系统，Kaczmarz++捕获大型异常奇异值的速度均快于主流Krylov方法。同时开发了针对半正定系统的优化变体CD++，在基准问题集上其算术运算效率与共轭梯度法(CG)和广义最小残差法(GMRES)具有竞争力。
为实现这些结果，研究团队对Kaczmarz框架引入了多项创新改进：
- 自适应动量加速技术
- Tikhonov正则化投影方法
- 用于重用历史方程块信息的记忆化方案
方法细节
核心算法架构
Kaczmarz++采用块随机采样策略，通过加权概率分布选择方程块，其中权重与块的行范数平方成正比。每次迭代执行以下操作：
- 采样方程块$A_i$
- 计算Tikhonov正则化投影：$x_{k+1} = x_k - A_i^T(A_i A_i^T + \lambda I)^{-1}(A_i x_k - b_i)$
- 应用自适应动量项：$v_{k+1} = \beta_k v_k + (1-\beta_k)(x_{k+1}-x_k)$
- 更新迭代点：$x_{k+1} = x_k + v_{k+1}$
收敛性分析
理论证明显示，当存在$r$个显著异常奇异值时，Kaczmarz++的收敛速度达到$O(\exp(-k/r))$，而传统Krylov方法为$O(\exp(-k/\sqrt{r}))$。对于条件数为$\kappa$的矩阵，算法复杂度为$O(\kappa \log(1/\epsilon))$。
记忆化机制
设计滑动窗口缓存存储最近使用的$m$个方程块及其对应的投影矩阵$(A_i A_i^T + \lambda I)^{-1}$，减少重复计算开销达40%。
实验验证
在LibSVN数据集和SuiteSparse矩阵集合上的测试表明：
- 对于病态系统（$\kappa > 10^6$），Kaczmarz++比随机坐标下降快3.2倍
- 在神经网络训练问题中，CD++变体比标准共轭梯度法减少18%迭代次数
- 记忆化方案降低算术运算量达27%
应用前景
该方法特别适用于大规模机器学习问题，包括：
- 分布式线性系统求解
- 随机优化问题
- 图像重建与计算机视觉
- 推荐系统矩阵补全