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

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.

Keywords

Inconsistent linear systems / Least-squares problem / Coordinate descent (CD) method / Convergence property / 65F10 / 65F20 / 65K05 / 90C25 / 15A06

References

[1] BaiZ-Z, LiuX-G. On the Meany inequality with applications to convergence analysis of several row-action iteration methods. Numer. Math., 2013, 124: 215-236

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

[3] BaiZ-Z, WangL, MuratovaGV. On relaxed greedy randomized augmented Kaczmarz methods for solving large sparse inconsistent linear systems. East Asian J. Appl. Math., 2022, 12: 323-332

[4] BaiZ-Z, WangL, WuW-T. On convergence rate of the randomized Gauss-Seidel method. Linear Algebra Appl., 2021, 611: 237-252

[5] BaiZ-Z, WuW-T. On greedy randomized Kaczmarz method for solving large sparse linear systems. SIAM J. Sci. Comput., 2018, 40: A592-A606

[6] BaiZ-Z, WuW-T. On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems. Linear Algebra Appl., 2019, 578: 225-250

[7] BaiZ-Z, WuW-T. On greedy randomized coordinate descent methods for solving large linear least-squares problems. Numer. Linear Algebra Appl., 2019, 26e2237

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

[9] BaiZ-Z, WuW-T. Randomized Kaczmarz iteration methods: algorithmic extensions and convergence theory. Jpn. J. Ind. Appl. Math., 2023, 40: 1421-1443

[10] BoydS, VandenbergheLConvex Optimization, 2004, Cambridge. Cambridge University Press.

[11] DavisTA, HuY. The University of Florida sparse matrix collection. ACM Trans. Math. Softw., 2011, 38: 1-25

[12] DuK, SiW-T, SunX-H. Randomized extended average block Kaczmarz for solving least squares. SIAM J. Sci. Comput., 2020, 42: A3541-A3559

[13] HefnyA, NeedellD, RamdasA. Rows versus columns: randomized Kaczmarz or Gauss-Seidel for ridge regression. SIAM J. Sci. Comput., 2017, 39: S528-S542

[14] HuangD-P, ZhangL. Least squares support vector machines with model uncertainty. Pattern Recognit., 2018, 78: 61-74

[15] IvanovAA, ZhdanovAI. Kaczmarz algorithm for Tikhonov regularization problem. Appl. Math. E-Notes, 2013, 13: 270-276

[16] Kaczmarz, S.: Angen$\ddot{{\rm a}}$herte aufl$\ddot{{\rm o}}$sung von systemen linearer gleichungen. Bull. Int. Acad. Pol. Sic. Let. Cl. Sci. Math. Nat. Ser. A Sci. Math. 35, 355–357 (1937)

[17] LeventhalD, LewisAS. Randomized methods for linear constraints: convergence rates and conditioning. Math. Oper. Res., 2010, 35: 641-654

[18] LiR-R, LiuH. On randomized partial block Kaczmarz method for solving huge linear algebraic systems. Comput. Appl. Math., 2022, 41: 1-10

[19] LiuY, GuC-Q. Variant of greedy randomized Kaczmarz for ridge regression. Appl. Numer. Math., 2019, 143: 223-246

[20] LuZ-S, XiaoL. On the complexity analysis of randomized block-coordinate descent methods. Math. Program., 2015, 152: 615-642

[21] MaA, NeedellD, RamdasA. Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods. SIAM J. Matrix Anal. Appl., 2015, 36: 1590-1604

[22] NecoaraI, NesterovY, GlineurF. Random block coordinate descent methods for linearly constrained optimization over networks. J. Optim. Theory Appl., 2017, 173: 227-254

[23] NeedellD, ZhaoR, ZouziasA. Randomized block Kaczmarz method with projection for solving least squares. Linear Algebra Appl., 2015, 484: 322-343

[24] NesterovY, StichSU. Efficiency of the accelerated coordinate descent method on structured optimization problems. SIAM J. Optim., 2017, 27: 110-123

[25] PopaC. Least-squares solution of overdetermined inconsistent linear systems using Kaczmarz’s relaxation. Int. J. Comput. Math., 1995, 55: 79-89

[26] PopaC. Extensions of block-projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems. BIT Numer. Math., 1998, 38: 151-176

[27] RichtárikP, TakáčM. Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. Math. Program., 2014, 144: 1-38

[28] RuheA. Numerical aspects of Gram-Schmidt orthogonalization of vectors. Linear Algebra Appl., 1983, 52: 591-601

[29] StrohmerT, VershyninR. A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl., 2009, 15: 262-278

[30] TikhonovAN, ArseninVYSolutions of Ill-Posed Problem, 1977, New York. Wiley.

[31] WuN-C, XiangH. Projected randomized Kaczmarz methods. J. Comput. Appl. Math., 2020, 372112672

[32] WuW-T. On two-subspace randomized extended Kaczmarz method for solving large linear least-squares problems. Numer. Algorithms, 2022, 89: 1-31

[33] ZhangJ-H, GuoJ-H. On relaxed greedy randomized coordinate descent methods for solving large linear least-squares problems. Appl. Numer. Math., 2020, 157: 372-384

[34] ZouziasA, FrerisNM. Randomized extended Kaczmarz for solving least squares. SIAM J. Matrix Anal. Appl., 2013, 34: 773-793

Funding

National Natural Science Foundation of China(11401305)

Shenzhen Science and Technology Program(JCYJ20230807142002006)

RIGHTS & PERMISSIONS

Shanghai University