2025/06/19 by Zhang, Xin-Fang, Xiao, Meng-Long, Li, Tao
Computer Science · Engineering · Mathematics · #65F10 #65F20 #94A08 #Advanced Optimization Algorithms Research #FOS: Mathematics #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2506.16106
openalex publication_date 2025/06/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The randomized extended Kaczmarz method, proposed by Zouzias and Freris (SIAM J. Matrix Anal. Appl. 34: 773-793, 2013), is appealing for solving least-squares problems. However, its randomly selecting rows and columns of A with probability proportional to their squared norm is unattractive compared to the greedy strategy. In this paper, we first consider a novel two-dimensional greedy randomized extended Kaczmarz method for solving large linear least-squares problems. The proposed method randomly selects two rows and two columns of A by grasping two larger entries in the magnitude of the corresponding residual vector per iteration. To improve its convergence, we then propose a two-dimensional semi-randomized extended Kaczmarz method and its modified version with simple random sampling, which is particularly favorable for big data problems. The convergence analysis of which is also established. Numerical results on some practical applications illustrate the superiority of the proposed methods compared with state-of-the-art randomized extended Kaczmarz methods, especially in terms of computing time.