The Study Of Convergence Rate Of Randomized Sparse Kaczmarz Method

The problem of solving linear equations is an important subject of research and discussion in the field of numerical algebra.Since many practical problems can be transformed into solving problems of linear equations,new methods for solving linear equations emerge in endlessly.Most of the existing solving methods use the column's information of the coefficient matrix of the linear equations or the information of the entire coefficient matrix to solve the linear equations in a direct or iterative manner.Kaczmarz took a novel approach and proposed the Kaczmarz method of row iteration.This method only uses the information of one equation of the linear equations in each iteration,which greatly reduces the amount of computation.However,the convergence rate of this method depends heavily on the order of the equation in the linear equations.In order to solve this problem,the randomized Kaczmarz method came into being.Based on this,the randomized sparse Kaczmarz method for solving the sparse solution of linear equations has also been studied in depth.Existing papers have proved that the sequence generated by the randomized Kaczmarz method and the sequence generated by the randomized sparse Kaczmarz method linearly converge to the least 2-norm solution and the sparse solution of the linear equations in the expected sense.Unfortunately,the convergence of the two methods has not been proven and the analysis of the convergence rate of the randomized sparse Kaczmarz method in the existing literature is not accurate.Considering what is the connection between the two methods as variants of the Kaczmarz method? If the two methods are related,what is the relationship between the convergence rates of the two methods? This is the content discussed in this article.Based on this,this paper proves the almost sure convergence of the randomized Kaczmarz method and the randomized sparse Kaczmarz method.In other words,the probability that the sequence generated by the randomized Kaczmarz method and the sequence generated by the randomized sparse Kaczmarz method converge to the solution of the linear equations is 1.And this paper reanalyzes the convergence rate of the randomized sparse Kaczmarz method.These conclusions provide theoretical support for the two methods to solve linear equations.Moreover,this paper makes corresponding corrections based on the analysis of the results of the convergence rate of the randomized sparse Kaczmarz method in the existing literature.At last,this paper points out that under the certain condition,the randomized sparse Kaczmarz method degenerates to the randomized Kaczmarz method.However,the convergence rates of the two methods is incompatible,that is,the convergence rate of the randomized sparse Kaczmarz method is slower than that of the randomized Kaczmarz method.