Fast Randomized Kaczmarz-type Methods For Solving Large Scale Linear Systems

The fast solution of large-scale linear systems has become important in efficient numerical algorithms from big data analysis and machine learning.In this dissertation,by using randomized matrix,matrix Sketching,randomized approximation,probability statistics and numerical algebra,we propose some fast randomized Kaczmarz-type methods for solving large-scale linear systems.The main contributions are described as follows.For large overdetermined consistent linear systems,firstly,the fast greedy block Kaczmarz method(CGBK)is proposed based on CountSketch transform and an approximate greedy criterion.Then,convergence theory of CGBK method is given and it is compared with greedy block Kaczmarz method(GBK)in detail.Secondly,in order to overcome the faultiness that GBK method contains pseudoinverse computation and is not adequate for distributed implementations,a pseudoinverse-free greedy block Kaczmarz method(FGBK)for solving large overdetermined consistent systems is developed based on projection average weighting technique.Then,convergence properties of the FGBK method is given.Finally,in order to accelerate convergence rate of FGBK method,using matrix Sketching techniques,we establish a faster FGBK method.In addition,its convergence property is presented.Numerical experiments are tested to demonstrate the effectiveness of the new methods for solving large-scale overdetermined consistent linear systems.For large overdetermined inconsistent linear systems,firstly,by using randomized matrix,randomized approximation,probability and statistics,we establish numerical approximation properties of CountSketch transformation.Secondly,by embedding CountSketch transform into REKS method,a fast randomized extended Kaczmarz method(CREKS)for solving large-scale overdetermined inconsistent linear systems is established.Then,convergence theory and specific solving process of CREKS method are analyzed.Finally,numerical experiments are provided to show that the convergence rate of CREKS method is faster than that of REKS method in terms of computing times.