求解线性方程组稀疏解的稀疏贪婪随机Kaczmarz算法

Sparse Greedy Randomized Kaczmarz Method for Sparse Solutions to Linear Equations

摘要:

求解线性方程组的稀疏解在图像重构、信号处理和机器学习等领域中具有广泛的应用，通过引入l1-范数正则化，可以转化为求解一个约束优化问题。基于一种选择系数矩阵工作行的概率准则，提出了稀疏贪婪随机Kaczmarz算法，并给出了有噪声干扰和无噪声干扰情况下该算法的收敛性分析。理论表明本文算法的收缩因子小于随机稀疏Kaczmarz算法的收缩因子。数值实验验证了本文算法的有效性。

Abstract:

The sparse solution to linear equations has been widely used in image reconstruction， signal processing， and machine learning. By introducing l1 norm regularization， it can be transformed into solving a constrained optimization problem. Based on a novel probability criterion for selecting the working rows from the coefficient matrix， a sparse greedy randomized Kaczmarz method was proposed， and the convergence analysis of the novel method with and without noise interference were conducted， which showed that the convergence factor of the novel method was smaller than that of the randomized sparse Kaczmarz method. The numerical experiments verified the effectiveness of the proposed method.