| Randomized Kaczmarz algorithm(RK)is an effective method for solving large-scale linear equations.It has gained wide attention and applications because of its advantages in calculation and storage.However,its probability selection is affected by the norm of the row of the matrix.There are two types of effective algorithms proposed to improve the RK algorithm currently: The one is to make probability selection directly based on the residuals,and the other is the greedy randomized algorithm that combines the greedy method with the randomized method.This thesis improves the existing algorithms based on the above two types of algorithms.First of all,this thesis improves the new randomized Kaczmarz algorithm(NRK)which is based on the 1-norm of the residual,and proposes the NRK2 algorithm based on the 2-norm of the residual.Without the condition of normalization,it is proved that the NRK2 algorithm converges with expected linear rate and the convergence rate is better than the RK algorithm and the NRK algorithm.The experiment verifies the superiority of the NRK2 algorithm in term of the number of the iterations and running time.Secondly,this thesis proposes the greedy new randomized Kaczmarz algorithm(GNRK)and the greedy new randomized coordinate descent algorithm(GNRCD)based on the new randomized algorithm combined with the greedy algorithm,and proves the convergence of the GNRK algorithm and the GNRCD algorithm.In addition,numerical experiments show that the GNRK and the GNRCD algorithms are slightly better than the greedy randomized Kaczmarz algorithm(GRK)and the greedy randomized coordinate descent algorithm(GRCD).Finally,the randomized Kaczmarz algorithm with oblique projection(RKO)has advantages in dealing with the problems when the system has correlated rows.This thesis uses the relaxation thought and the online learning theory to study the RKO algorithm in the least squares regression setting.When the sampling process is noisy or nonlinear,the necessary condition on the sequence of relaxation parameters for the convergence of the algorithm in expectation is presented. |
