A Note on Randomized Kaczmarz Algorithm for Solving Doubly-Noisy Linear Systems

解决问题：本篇论文旨在解决含有噪声的线性系统求解问题，特别是当系数矩阵A受到加性和乘性噪声干扰时，如何使用随机Kaczmarz算法进行求解。这是一个新问题，因为之前的研究只考虑了右手边向量b中的测量噪声，而忽略了系数矩阵A的噪声干扰。

关键思路：本文提出了一种分析随机Kaczmarz算法在含有噪声的线性系统中的收敛性的方法，该方法不需要关于无噪声系数矩阵A的信息，可以控制算法的收敛性。与当前领域的研究相比，本文的思路在于考虑了系数矩阵A的噪声干扰，并提出了一种新的分析方法。

其他亮点：本文通过大量的数值实验验证了理论结果的正确性，并提供了开源的代码。该研究对于实际应用中含有噪声的线性系统求解具有重要意义，值得进一步深入研究。

相关研究：与本文相关的研究包括： "A randomized Kaczmarz algorithm for solving linear systems with exponential convergence" (Strohmer and Vershynin, 2009) 和 "Convergence analysis of randomized Kaczmarz algorithm for inconsistent linear systems" (Liu et al., 2013)。

论文摘要：本文研究了在实践中经常出现的含噪线性系统$Ax=b$的迭代求解问题。过去十年中，随机Kaczmarz（RK）算法被广泛研究并应用于这类系统的高效求解。然而，RK算法在噪声情况下的收敛性研究有限，仅考虑右手边向量$b$的测量噪声。而在实践中，系数矩阵$A$也可能存在噪声。本文分析了当系数矩阵$A$和向量$b$都含有加性和乘性噪声时，RK算法的收敛性。在分析中，量$\tilde R=| \tilde A^{\dagger} |2^2 |\tilde A |F^2$影响了RK算法的收敛性，其中$\tilde A$表示$A$的噪声版本。本文认为我们的分析具有鲁棒性和现实适用性，因为我们不需要关于无噪声系数矩阵$A$的信息，并且可以通过考虑不同的噪声条件来控制RK算法的收敛性。我们通过进行全面的数值实验来验证了我们的理论发现。

内容中包含的图片若涉及版权问题，请及时与我们联系删除