A Maximal Residual Two Subspace Projection Algorithm for Solving Least-Squares Problems

doi:10.1007/s42967-025-00495-1

Communications on Applied Mathematics and Computation ›› 2026, Vol. 8 ›› Issue (3): 1226-1242.doi: 10.1007/s42967-025-00495-1

• • 上一篇

A Maximal Residual Two Subspace Projection Algorithm for Solving Least-Squares Problems

Ashif Mustafa, Manideepa Saha

Department of Mathematics, National Institute of Technology Meghalaya, Laitumkhrah, Shillong, Meghalaya, 793003, India

收稿日期:2024-05-07 修回日期:2025-02-19 出版日期:2026-06-20 发布日期:2026-05-29
通讯作者: Manideepa Saha, Email: manideepa.saha@nitm.ac.in E-mail:manideepa.saha@nitm.ac.in
作者简介:Ashif Mustafa, Email: ashifmustafa@nitm.ac.in

A Maximal Residual Two Subspace Projection Algorithm for Solving Least-Squares Problems

Ashif Mustafa, Manideepa Saha

Department of Mathematics, National Institute of Technology Meghalaya, Laitumkhrah, Shillong, Meghalaya, 793003, India

Received:2024-05-07 Revised:2025-02-19 Online:2026-06-20 Published:2026-05-29
Contact: Manideepa Saha, Email: manideepa.saha@nitm.ac.in E-mail:manideepa.saha@nitm.ac.in

摘要/Abstract

摘要： We study a greedy coordinate descent method to solve large linear least-squares problems expanding on a randomized coordinate descent method presented by Leventhal and Lewis (Math. Oper. Res. 35: 641-654, 2010). For an overdetermined system, they proved its exponential convergence, regardless of its consistency. In our work, we study a greedy selection rule for the coordinate descent method which we refer to as the two-dimensional maximal residual Gauss-Seidel (D2MRGS) method. In this method, we select two coordinates in every iteration and treat the current approximation in those directions. Convergence is analyzed for the stated method and numerical experiments are provided to demonstrate its efficiency.

关键词: Coordinate descent, Iterative techniques, Least-squares problem, Petrov-Galerkin condition, Projection methods, Randomized methods

Abstract: We study a greedy coordinate descent method to solve large linear least-squares problems expanding on a randomized coordinate descent method presented by Leventhal and Lewis (Math. Oper. Res. 35: 641-654, 2010). For an overdetermined system, they proved its exponential convergence, regardless of its consistency. In our work, we study a greedy selection rule for the coordinate descent method which we refer to as the two-dimensional maximal residual Gauss-Seidel (D2MRGS) method. In this method, we select two coordinates in every iteration and treat the current approximation in those directions. Convergence is analyzed for the stated method and numerical experiments are provided to demonstrate its efficiency.

Key words: Coordinate descent, Iterative techniques, Least-squares problem, Petrov-Galerkin condition, Projection methods, Randomized methods

中图分类号:

Ashif Mustafa, Manideepa Saha. A Maximal Residual Two Subspace Projection Algorithm for Solving Least-Squares Problems[J]. Communications on Applied Mathematics and Computation, 2026, 8(3): 1226-1242.

参考文献

[1] Bai, Z.-Z., Wang, L.: On convergence rates of Kaczmarz-type methods with different selection rules of working rows. Appl. Numer. Math. 186, 289-319 (2023)
[2] Bai, Z.-Z., Wang, L.: On multi-step randomized extended Kaczmarz method for solving large sparse inconsistent linear systems. Appl. Numer. Math. 192, 197-213 (2023)
[3] Bai, Z.-Z., Wu, W.-T.: On greedy randomized Kaczmarz method for solving large sparse linear systems. SIAM J. Sci. Comput. 40, A592-A606 (2018)
[4] Bai, Z.-Z., Wu, W.-T.: On greedy randomized coordinate descent methods for solving large linear least-squares problems. Numer. Linear Algebra Appl. 26, e2237 (2019)
[5] Bai, Z.-Z., Wu, W.-T.: On greedy randomized augmented Kaczmarz method for solving large sparse inconsistent linear systems. SIAM J. Sci. Comput. 43, A3892-A3911 (2021)
[6] Bai, Z.-Z., Wu, W.-T.: Randomized Kaczmarz iteration methods: algorithmic extensions and convergence theory. Jpn. J. Ind. Appl. Math. 40, 1421-1443 (2023)
[7] Du, K.: Tight upper bounds for the convergence of the randomized extended Kaczmarz and Gauss-Seidel algorithms. Numer. Linear Algebra Appl. 26, 1-14 (2019)
[8] Jin, L.-L., Li, H.-B.: Greedy double subspaces coordinate descent method for solving linear least-squares problems. J. Comput Sci. 70, 102029 (2023)
[9] Kaczmarz, S.: Angenäherte auösung von systemen linearer gleichungen. Bull. Int. Acad. Polom. Sci. Lett. A 35, 355-357 (1937)
[10] Kaczmarz, S.: Approximate solution of systems of linear equations. Int. J. Control 57, 1269-1271 (1993)
[11] Leventhal, D., Lewis, A.S.: Randomized methods for linear constraints: convergence rates and conditioning. Math. Oper. Res. 35, 641-654 (2010)
[12] Liao, Y.-M., Lu, T.-X., Yin, F.: A two-step randomized Gauss-Seidel method for solving large-scale linear least squares problems. Electron. Res. Arch. 30, 755-779 (2022)
[13] Liu, Y., Jiang, X.-L., Gu, C.-Q.: On maximum residual block and two-step Gauss-Seidel algorithms for linear least-squares problems. Calcolo 58, 13 (2021)
[14] Lv, Z., Bao, W., Li, W., Wang, F., Wu, G.: On extended Kaczmarz methods with random sampling and maximum-distance for solving large inconsistent linear systems. Results Appl. Math. 13, 100240 (2022)
[15] Ma, A., Needell, D., Ramdas, A.: Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods. SIAM J. Matrix Anal. Appl. 36, 1590-1604 (2015)
[16] Mustafa, A., Saha, M.: A generalized projection iterative method for solving non-singular linear systems. Math. Found. Comput. 5, 343-350 (2022)
[17] Mustafa, A., Saha, M.: A two dimensional randomized extended Gauss-Seidel algorithm for solving least squares problems. Numer. Algorithm 96, 665-686 (2023)
[18] Mustafa, A., Saha, M.: Maximal residual extended Kaczmarz and Gauss-Seidel methods-convergence properties and applications. J. Comput. Appl. Math. 448, 115920 (2024)
[19] Needell, D., Ward, R.: Two-subspace projection method for coherent overdetermined systems. J. Fourier Anal. Appl. 19, 256-269 (2013)
[20] Niu, Y.-Q., Zheng, B.: A new randomized Gauss-Seidel method for solving linear least-squares problems. Appl. Math. Lett. 116, 107057 (2021)
[21] Popa, C.: Convergence rates for Kaczmarz-type algorithms. Numer. Algorithm 79, 1-17 (2018)
[22] Saad, Y.: Iterative Methods for Sparse Linear Systems, 2nd edn. SIAM, Philadelphia (2003)
[23] Strohmer, T., Vershynin, R.: A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. 15, 262-278 (2009)
[24] Watkins, D.S.: Fundamentals of Matrix Computations, 2nd edn. Wiley, New York (2004)
[25] Wu, W.: Paving the randomized Gauss-Seidel method. BSc Thesis, Scripps College, Claremont, California (2017)
[26] Wu, W.-T.: On two-subspace randomized extended Kaczmarz method for solving large linear least-squares problems. Numer. Algorithm 89, 1-31 (2022)
[27] Zouzias, A., Freris, N.M.: Randomized extended Kaczmarz for solving least squares. SIAM J. Matrix Anal. Appl. 34, 773-793 (2013)

A Maximal Residual Two Subspace Projection Algorithm for Solving Least-Squares Problems

A Maximal Residual Two Subspace Projection Algorithm for Solving Least-Squares Problems

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

本文评价

[1]	Qian-Nan Lian, Ju-Li Zhang. A Count Column Sketch Method for Tensor Auto-regression Parameter Estimation[J]. Communications on Applied Mathematics and Computation, 2025, 7(5): 2137-2155.
[2]	Ran-Ran Li, Hao Liu. On Cyclic Block Coordinate Descent Method for Solving Large Inconsistent Linear Systems[J]. Communications on Applied Mathematics and Computation, 2025, 7(5): 1993-2006.
[3]	Chao Sun, Xiao-Xia Guo. A Novel Greedy Block Gauss-Seidel Method for Solving Large Linear Least-Squares Problems[J]. Communications on Applied Mathematics and Computation, 2025, 7(5): 1959-1976.
[4]	Jingrun Chen, Weinan E, Yifei Sun. Optimization of Random Feature Method in the High-Precision Regime[J]. Communications on Applied Mathematics and Computation, 2024, 6(2): 1490-1517.