The Improvement And Application Of Randomized Kaczmarz Algorithm

Large over-determined linear equations are widely used in application fields,such as image reconstruction and digital signal processing.Kaczmarz algorithm is one of the classical iterative methods for solving large over-determined linear equations.This algorithm uses alternative projection method to iterate.Because of its simple algorithm and very fast running speed,it is widely used in many practical problems.The randomized Kaczmarz algorithm,the RK algorithm for short,has higher efficiency and converges exponentially as expected.The RK algorithm sometimes only needs to use some rows of the coefficient matrix to solve the system of equations.Numerical experiments and theoretical analysis have shown that under certain conditions,the RK algorithm is more efficient than the well-known conjugate gradient algorithm.For different large over-determined linear equations,the direct use of the RK algorithm to solve them is sometimes not very good.This depends on the coefficient matrix of the large over-determined linear equations.The theoretical analysis of its convergence is not particularly perfect.Therefore,improving the RK algorithm,thereby increasing its iteration efficiency,has become one of the main research contents of the RK algorithm and has important practical significance.This article mainly studies the improvement and application of RK algorithm as follows:1.Improvement based on RKJL algorithmA new improved RK algorithm,namely modified RKJL algorithm(MRKJL algorithm),is proposed by improving the method of selecting rows in RKJL algorithm.Theoretically analyzed that MRKJL algorithm is convergent.Two numerical experiments verify that the convergence speed of the MRKJL algorithm is faster than the RKJL algorithm and the RK algorithm.2.Improvement based on BRK algorithmBy improving the selection of block sub-matrix in BRK algorithm,an improved RK algorithm,namely modified BRK algorithm(MBRK algorithm),is proposed.And the rationality of the MBRK algorithm is illustrated in this paper.Numerical experiments verify that MBRK algorithm has better convergence than BRK algorithm and RK algorithm.3.Applying RK algorithm to least squares data fittingWhen the experimental fitting data is huge,the essence of least squares data fitting is to solve an overdetermined linear equation system,using the RK algorithm to solve.Numerical experiments show that the fitting effect is very good.