Sparse Greedy Randomized Kaczmarz Method for Sparse Solutions to Linear Equations

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.

Key words:Kaczmarz method;sparse solution;convergence;randomized iteration