Preconditioning Greedy Kaczmarz Method Based on Count Sketch

Abstract:

The convergence rate of greedy Kaczmarz method can be improved by introducing right preconditioner through orthogonal triangularization of coefficient matrix. However， when the number of rows of the coefficient matrix is much larger than the number of columns， the cost of orthogonal triangularization is too high. By introducing Count Sketch transform， a preconditioning greedy Kaczmarz method based on Count Sketch is proposed to reduce the cost. Convergence analysis of the new algorithm is provided， and the theoretical analysis shows that the new method has better convergence rate than the existing method when the condition number of coefficient matrix is large. The numerical experiments verified the effectiveness.