ORIGINAL PAPERS

On Cyclic Block Coordinate Descent Method for Solving Large Inconsistent Linear Systems

  • Ran-Ran Li ,
  • Hao Liu
Expand
  • 1. School of Mathematics, Nanjing University of Aeronautics and Astronautics, Nanjing, 211106, Jiangsu, China;
    2. Shenzhen Research Institute, Shenzhen, 518063, Guangdong, China

Received date: 2024-01-12

  Revised date: 2024-05-17

  Accepted date: 2024-05-21

  Online published: 2024-09-19

Supported by

This research was supported in part by the National Natural Science Foundation of China (No. 11401305 and No. 11571171) and Shenzhen Science and Technology Program, China (No. JCYJ20230807142002006).

Abstract

For solving large inconsistent linear systems, we research a novel format to enhance the numerical stability and control the complexity of the model. Based on the idea of two subspace iterations, we propose the max-residual two subspace coordinate descent (M2CD) method. To accelerate the convergence rate, we further present the cyclic block coordinate descent (CBCD) method. The convergence properties of these methods are analyzed, and their effectiveness is illustrated by numerical examples.

Cite this article

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 . DOI: 10.1007/s42967-024-00432-8

References

[1] Bai, Z.-Z., Liu, X.-G.: On the Meany inequality with applications to convergence analysis of several row-action iteration methods. Numer. Math. 124, 215-236 (2013)
[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., Wang, L., Muratova, G.V.: On relaxed greedy randomized augmented Kaczmarz methods for solving large sparse inconsistent linear systems. East Asian J. Appl. Math. 12, 323-332 (2022)
[4] Bai, Z.-Z., Wang, L., Wu, W.-T.: On convergence rate of the randomized Gauss-Seidel method. Linear Algebra Appl. 611, 237-252 (2021)
[5] 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)
[6] Bai, Z.-Z., Wu, W.-T.: On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems. Linear Algebra Appl. 578, 225-250 (2019)
[7] 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)
[8] 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)
[9] Bai, Z.-Z., Wu, W.-T.: Randomized Kaczmarz iteration methods: algorithmic extensions and convergence theory. Jpn. J. Ind. Appl. Math. 40, 1421-1443 (2023)
[10] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)
[11] Davis, T.A., Hu, Y.: The University of Florida sparse matrix collection. ACM Trans. Math. Softw. 38, 1-25 (2011)
[12] Du, K., Si, W.-T., Sun, X.-H.: Randomized extended average block Kaczmarz for solving least squares. SIAM J. Sci. Comput. 42, A3541-A3559 (2020)
[13] Hefny, A., Needell, D., Ramdas, A.: Rows versus columns: randomized Kaczmarz or Gauss-Seidel for ridge regression. SIAM J. Sci. Comput. 39, S528-S542 (2017)
[14] Huang, D.-P., Zhang, L.: Least squares support vector machines with model uncertainty. Pattern Recognit. 78, 61-74 (2018)
[15] Ivanov, A.A., Zhdanov, A.I.: Kaczmarz algorithm for Tikhonov regularization problem. Appl. Math. E-Notes 13, 270-276 (2013)
[16] Kaczmarz, S.: Angen\begin{document}$ \ddot{{\rm a}} $\end{document}herte aufl\begin{document}$ \ddot{{\rm o}} $\end{document}sung von systemen linearer gleichungen. Bull. Int. Acad. Pol. Sic. Let. Cl. Sci. Math. Nat. Ser. A Sci. Math. 35, 355-357 (1937)
[17] Leventhal, D., Lewis, A.S.: Randomized methods for linear constraints: convergence rates and conditioning. Math. Oper. Res. 35, 641-654 (2010)
[18] Li, R.-R., Liu, H.: On randomized partial block Kaczmarz method for solving huge linear algebraic systems. Comput. Appl. Math. 41, 1-10 (2022)
[19] Liu, Y., Gu, C.-Q.: Variant of greedy randomized Kaczmarz for ridge regression. Appl. Numer. Math. 143, 223-246 (2019)
[20] Lu, Z.-S., Xiao, L.: On the complexity analysis of randomized block-coordinate descent methods. Math. Program. 152, 615-642 (2015)
[21] 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)
[22] Necoara, I., Nesterov, Y., Glineur, F.: Random block coordinate descent methods for linearly constrained optimization over networks. J. Optim. Theory Appl. 173, 227-254 (2017)
[23] Needell, D., Zhao, R., Zouzias, A.: Randomized block Kaczmarz method with projection for solving least squares. Linear Algebra Appl. 484, 322-343 (2015)
[24] Nesterov, Y., Stich, S.U.: Efficiency of the accelerated coordinate descent method on structured optimization problems. SIAM J. Optim. 27, 110-123 (2017)
[25] Popa, C.: Least-squares solution of overdetermined inconsistent linear systems using Kaczmarz’s relaxation. Int. J. Comput. Math. 55, 79-89 (1995)
[26] Popa, C.: Extensions of block-projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems. BIT Numer. Math. 38, 151-176 (1998)
[27] Richtárik, P., Takáč, M.: Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. Math. Program. 144, 1-38 (2014)
[28] Ruhe, A.: Numerical aspects of Gram-Schmidt orthogonalization of vectors. Linear Algebra Appl. 52, 591-601 (1983)
[29] Strohmer, T., Vershynin, R.: A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. 15, 262-278 (2009)
[30] Tikhonov, A.N., Arsenin, V.Y.: Solutions of Ill-Posed Problem. Wiley, New York (1977)
[31] Wu, N.-C., Xiang, H.: Projected randomized Kaczmarz methods. J. Comput. Appl. Math. 372, 112672 (2020)
[32] Wu, W.-T.: On two-subspace randomized extended Kaczmarz method for solving large linear least-squares problems. Numer. Algorithms 89, 1-31 (2022)
[33] Zhang, J.-H., Guo, J.-H.: On relaxed greedy randomized coordinate descent methods for solving large linear least-squares problems. Appl. Numer. Math. 157, 372-384 (2020)
[34] Zouzias, A., Freris, N.M.: Randomized extended Kaczmarz for solving least squares. SIAM J. Matrix Anal. Appl. 34, 773-793 (2013)
Options
Outlines

/