揭示随机Kaczmarz算法在噪声系统中的收敛极限位置
Where Have All the Kaczmarz Iterates Gone?
- 分析噪声下系数矩阵奇异向量对迭代轨迹的影响
- 推导收敛范围边界，与噪声水平和系统特性相关
- 为工程应用提供噪声环境下的算法性能参考
随机Kaczmarz（RK）算法是求解大规模线性系统最高效、内存占用最低的迭代方法之一。然而实际应用中常面临含噪且可能不一致的系统。尽管对一致系统的收敛性已有充分理解，但对噪声不一致系统的研究仍有限。本文研究了在噪声不一致系统中，RK迭代序列在期望下的渐近行为，明确了其极限点的位置。通过分析（噪声）系数矩阵的奇异向量作用，推导出收敛范围的上界，该边界依赖于噪声水平与系统特征。最后，通过大量数值实验验证了理论结果，为算法在真实条件下的表现提供了实践洞察。这些成果深化了对RK算法在噪声环境中局限性与鲁棒性的理解，为科学与工程领域的优化应用奠定基础。
原文摘要 · Abstract (English)
The randomized Kaczmarz (RK) algorithm is one of the most computationally and memory-efficient iterative algorithms for solving large-scale linear systems. However, practical applications often involve noisy and potentially inconsistent systems. While the convergence of RK is well understood for consistent systems, the study of RK on noisy, inconsistent linear systems is limited. This paper investigates the asymptotic behavior of RK iterates in expectation when solving noisy and inconsistent systems, addressing the locations of their limit points. We explore the roles of singular vectors of the (noisy) coefficient matrix and derive bounds on the convergence horizon, which depend on the noise levels and system characteristics. Finally, we provide extensive numerical experiments that validate our theoretical findings, offering practical insights into the algorithm's performance under realistic conditions. These results establish a deeper understanding of the RK algorithm's limitations and robustness in noisy environments, paving the way for optimized applications in real-world scientific and engineering problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。