Two-dimensional greedy randomized extended Kaczmarz methods
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918064271917056 |
|---|---|
| author | Zhang, Xin-Fang Xiao, Meng-Long Li, Tao |
| author_facet | Zhang, Xin-Fang Xiao, Meng-Long Li, Tao |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_16106 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Two-dimensional greedy randomized extended Kaczmarz methods Zhang, Xin-Fang Xiao, Meng-Long Li, Tao Numerical Analysis 65F10, 65F20, 94A08 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. |
| title | Two-dimensional greedy randomized extended Kaczmarz methods |
| topic | Numerical Analysis 65F10, 65F20, 94A08 |
| url | https://arxiv.org/abs/2506.16106 |