Study On Numerical Algorithms And Their Applications In Kaczmarz Algorithm

Kaczmarz algorithm is an effective method for solving overdetermined linear system Ax = b.In the field of information science,such as image reconstruction,digital signal processing,we have a wide range of applications.Compared with the traditional Kaczmarz algorithm,the efficiency of RK algorithm is more efficient,the convergence speed can reach exponential convergence.For certain conditions overdetermined linear system,RK algorithm is more efficient than conjugate gradient.This paper further study randomized RK algorithm design,and innovative works include:1.An accelerated randomized Kaczmarz method via low-rank approximationMotivated by idea of precondition,we present a modified version of the randomized Kaczmarz method where an orthogonal matrix was multiplied to both sides of the equation Ax = b,and the orthogonal matrix is obtained by low-rank approximation.Our approach fits the problem when m is huge and m ? n.Theoretically,we improve the convergence rate of the randomized Kaczmarz method.The numerical results show that our approach is faster than the standard randomized Kaczmarz.2.An Accelerated Randomized Extended Kaczmarz AlgorithmIt was proved that for inconsistent linear system,with randomized orthogonal projection,the randomized extended Kaczmarz?REK?method converges with an expected exponential rate.We describe an accelerated randomized Extended Kaczmarz algorithm?AREK?with Nesterov's accelerated procedure.The analysis shows that AREK converges better than REK when A is dense and the smallest singular value of ATA is small.3.Row Subset Selection in Randomized Block Kaczmarz MethodNeedell and Tropp provided analysis of a randomized block Kaczmarz method.This paper describes row selection method controls the condition number and the condition number of each block.The contribution is that,based on random row selection and least squares method,by using appropriate scheme,each iteration of the block method can obtain better results for solving least squares in randomized block Kaczmarz method.4.A Subspace Embedding Method in L₂ Norm via Fast Cauchy TransformWe propose a subspace embedding method via Fast Cauchy Transform?FCT?in L₂ norm.It is motivated by and complements the work of the subspace embedding method.Unlike the traditionally used orthogonal basis in Johnson-Lindenstrauss?JL?embedding,we employ the well-conditioned basis in L₂ norm to obtain concentration property of FCT in L₂ norm.