Cosine distance-driven greedy block Gaussian-Kaczmarz algorithm and its variants for solving large-scale sparse overdetermined linear systems
摘要
To solve large-scale sparse overdetermined linear systems, the Kaczmarz algorithm is a well-established and effective iterative method. Based on the residual-driven greedy deterministic block Kaczmarz (FDBK) algorithm, this paper proposes an improved greedy selection strategy. The greedy criterion in the FDBK algorithm mainly depends on the residual size, which is susceptible to numerical errors and ignores the direction information. Accordingly, this paper employs cosine distance as a geometric criterion to capture the angular relationship between the current solution and the candidate hyperplane, and develops a cosine distance-driven greedy block Gaussian-Kaczmarz (CD-GBGK) algorithm. The algorithm introduces a relaxation factor, further summarizes the CD-GBGK algorithm, and proves that the algorithm converges to its unique minimum norm solution when the equations are consistent. In this paper, it is also proved in theory and numerical experiments that the performance of the CD-rGBGK algorithm is optimal when the relaxation factor is 0. Theoretical analysis shows that the algorithm has linear convergence, and numerical experiments further verify that it can significantly reduce the computational overhead and improve the computational efficiency while preserving the accuracy.