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

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.

Keywords

Coordinate descent / Iterative techniques / Least-squares problem / Petrov-Galerkin condition / Projection methods / Randomized methods / 15A06 / 65F10 / 65F20

References

[1] Bai Z-Z, Wang L. On convergence rates of Kaczmarz-type methods with different selection rules of working rows. Appl. Numer. Math., 2023, 186: 289-319

[2] Bai Z-Z, Wang L. On multi-step randomized extended Kaczmarz method for solving large sparse inconsistent linear systems. Appl. Numer. Math., 2023, 192: 197-213

[3] Bai Z-Z, Wu W-T. On greedy randomized Kaczmarz method for solving large sparse linear systems. SIAM J. Sci. Comput., 2018, 40: A592-A606

[4] Bai Z-Z, Wu W-T. On greedy randomized coordinate descent methods for solving large linear least-squares problems. Numer. Linear Algebra Appl., 2019, 26 Article ID: e2237

[5] Bai Z-Z, Wu W-T. On greedy randomized augmented Kaczmarz method for solving large sparse inconsistent linear systems. SIAM J. Sci. Comput., 2021, 43: A3892-A3911

[6] Bai Z-Z, Wu W-T. Randomized Kaczmarz iteration methods: algorithmic extensions and convergence theory. Jpn. J. Ind. Appl. Math., 2023, 40: 1421-1443

[7] Du K. Tight upper bounds for the convergence of the randomized extended Kaczmarz and Gauss-Seidel algorithms. Numer. Linear Algebra Appl., 2019, 26: 1-14

[8] Jin L-L, Li H-B. Greedy double subspaces coordinate descent method for solving linear least-squares problems. J. Comput Sci., 2023, 70 Article ID: 102029

[9] Kaczmarz S. Angenäherte auösung von systemen linearer gleichungen. Bull. Int. Acad. Polom. Sci. Lett. A, 1937, 35: 355-357

[10] Kaczmarz S. Approximate solution of systems of linear equations. Int. J. Control, 1993, 57: 1269-1271

[11] Leventhal D, Lewis AS. Randomized methods for linear constraints: convergence rates and conditioning. Math. Oper. Res., 2010, 35: 641-654

[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., 2022, 30: 755-779

[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, 2021, 58: 13

[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., 2022, 13 Article ID: 100240

[15] Ma A, Needell D, Ramdas A. Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods. SIAM J. Matrix Anal. Appl., 2015, 36: 1590-1604

[16] Mustafa A, Saha M. A generalized projection iterative method for solving non-singular linear systems. Math. Found. Comput., 2022, 5: 343-350

[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., 2024, 448 Article ID: 115920

[19] Needell D, Ward R. Two-subspace projection method for coherent overdetermined systems. J. Fourier Anal. Appl., 2013, 19: 256-269

[20] Niu Y-Q, Zheng B. A new randomized Gauss-Seidel method for solving linear least-squares problems. Appl. Math. Lett., 2021, 116 Article ID: 107057

[21] Popa, C.: Convergence rates for Kaczmarz-type algorithms. Numer. Algorithm 79, 1–17 (2018)

[22] Saad YIterative Methods for Sparse Linear Systems, 20032PhiladelphiaSIAM

[23] Strohmer T, Vershynin R. A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl., 2009, 15: 262-278

[24] Watkins DSFundamentals of Matrix Computations, 20042New YorkWiley

[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)

RIGHTS & PERMISSIONS

Shanghai University