Two-dimensional greedy randomized Kaczmarz methods for solving large-scale linear systems
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916811174313984 |
|---|---|
| author | Li, Tao Xiao, Meng-Long Zhang, Xin-Fang |
| author_facet | Li, Tao Xiao, Meng-Long Zhang, Xin-Fang |
| contents | In this paper, we consider a novel two-dimensional randomized Kaczmarz method and its improved version with simple random sampling, which chooses two active rows with probability proportional to the square of their cross-product-like constant, for solving large-scale linear systems. From the greedy selection strategy with grasping two larger entries of the residual vector at each iteration, we then devise a two-dimensional greedy randomized Kaczmarz method. To improve the above methods further, motivated by the semi-randomized Kaczmarz method and Chebyshev's law of large numbers, we propose a two-dimensional semi-randomized Kaczmarz method and its modified version with simple random sampling, which is particularly advantageous for big data problems. Theoretically, we prove that the proposed methods converge to the unique least-norm solution of the consistent linear systems. Numerical results on some practical applications illustrate the superiority of the proposed methods compared with some existing ones in terms of computing time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_20940 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Two-dimensional greedy randomized Kaczmarz methods for solving large-scale linear systems Li, Tao Xiao, Meng-Long Zhang, Xin-Fang Numerical Analysis 65F10, 65F20, 94A08 In this paper, we consider a novel two-dimensional randomized Kaczmarz method and its improved version with simple random sampling, which chooses two active rows with probability proportional to the square of their cross-product-like constant, for solving large-scale linear systems. From the greedy selection strategy with grasping two larger entries of the residual vector at each iteration, we then devise a two-dimensional greedy randomized Kaczmarz method. To improve the above methods further, motivated by the semi-randomized Kaczmarz method and Chebyshev's law of large numbers, we propose a two-dimensional semi-randomized Kaczmarz method and its modified version with simple random sampling, which is particularly advantageous for big data problems. Theoretically, we prove that the proposed methods converge to the unique least-norm solution of the consistent linear systems. Numerical results on some practical applications illustrate the superiority of the proposed methods compared with some existing ones in terms of computing time. |
| title | Two-dimensional greedy randomized Kaczmarz methods for solving large-scale linear systems |
| topic | Numerical Analysis 65F10, 65F20, 94A08 |
| url | https://arxiv.org/abs/2506.20940 |