A two-step randomized Gauss-Seidel method for solving large-scale linear least squares problems

Yimou Liao; Tianxiu Lu; Feng Yin; Yimou Liao; Tianxiu Lu; Feng Yin

doi:10.3934/era.2022040

Electronic Research Archive

2022, Volume 30, Issue 2: 755-779. doi: 10.3934/era.2022040

Previous Article Next Article

Research article Special Issues

A two-step randomized Gauss-Seidel method for solving large-scale linear least squares problems

1.
School of Mathematics and Statistics, Sichuan University of Science and Engineering, Zigong 643000, China
2.
Key Laboratory of Higher Education of Sichuan Province for Enterprise Informationalization and Internet of Things, Bridge Non-destruction Detecting and Engineering Computing Key Laboratory, Zigong 643000, China

Received: 20 December 2021 Revised: 11 February 2022 Accepted: 20 February 2022 Published: 28 February 2022

A two-step randomized Gauss-Seidel (TRGS) method is presented for large linear least squares problem with tall and narrow coefficient matrix. The TRGS method projects the approximate solution onto the solution space by given two random columns and is proved to be convergent when the coefficient matrix is of full rank. Several numerical examples show the effectiveness of the TRGS method among all methods compared.
- linear least-squares problem,
- two-step iterative method,
- convergence property,
- Gauss-Seidel
Citation: Yimou Liao, Tianxiu Lu, Feng Yin. A two-step randomized Gauss-Seidel method for solving large-scale linear least squares problems[J]. Electronic Research Archive, 2022, 30(2): 755-779. doi: 10.3934/era.2022040

Related Papers:

Abstract

A two-step randomized Gauss-Seidel (TRGS) method is presented for large linear least squares problem with tall and narrow coefficient matrix. The TRGS method projects the approximate solution onto the solution space by given two random columns and is proved to be convergent when the coefficient matrix is of full rank. Several numerical examples show the effectiveness of the TRGS method among all methods compared.

References

[1]	A. Björck, Numerical Methods for Least Squares Problems, SIAM, Philadelphia, 1996. https://doi.org/10.1137/1.9781611971484
[2]	A. Zouzias, N. M. Freris, Randomized extended Kaczmarz for solving least squares, SIAM J. Matrix Anal. Appl., 34 (2013), 773–793. https://doi.org/10.1137/120889897 doi: 10.1137/120889897
[3]	R. M. Gower, P. Richtarik, Randomized iterative methods for linear systems, SIAM J. Matrix Anal. Appl., 36 (2015), 1660-1690. https://doi.org/10.1137/15M1025487 doi: 10.1137/15M1025487
[4]	A. Ma, D. Needell, A. Ramdas, Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods, SIAM J. Matrix Anal. Appl., 36 (2015), 1590–1604. https://doi.org/10.1137/15M1014425 doi: 10.1137/15M1014425
[5]	Z. Z. Bai, W. T. Wu, On greedy randomized Kaczmarz method for solving large sparse linear systems, SIAM J. Sci. Comput., 40 (2018), A592–A606. https://doi.org/10.1137/17M1137747 doi: 10.1137/17M1137747
[6]	A. Ma, D. Needell, A. Ramdas, Iterative methods for solving factorized linear systems, SIAM J. Matrix Anal. Appl., 39 (2018), 104–122. https://doi.org/10.1137/17M1115678 doi: 10.1137/17M1115678
[7]	C. Byrne, A unified treatment of some iterative algorithms in signal processing and image reconstruction, Inverse Prob., 20 (2004), 103–120. https://doi.org/10.1088/0266-5611/20/1/006 doi: 10.1088/0266-5611/20/1/006
[8]	C. A. Bouman, K. Sauer, A unified approach to statistical tomography using coordinate descent optimization, IEEE Trans. Image Process., 5 (1996), 480–492. https://doi.org/10.1109/83.491321 doi: 10.1109/83.491321
[9]	J. C. Ye, K. J. Webb, C. A. Bouman, R. P. Millane, Optical diffusion tomography by iterative-coordinate-descent optimization in a Bayesian framework, J. Opt. Soc. Am. A., 16 (1999), 2400–2412. https://doi.org/10.1364/JOSAA.16.002400 doi: 10.1364/JOSAA.16.002400
[10]	A. A. Canutescu, R. L. Dunbrack, Cyclic coordinate descent: A robotics algorithm for protein loop closure, Protein Sci., 12 (2003), 963–972. https://doi.org/10.1110/ps.0242703 doi: 10.1110/ps.0242703
[11]	K. W. Chang, C. J. Hsieh, C. J. Lin, Coordinate descent method for large-scale L2-loss linear support vector machines, J. Mach. Learn. Res., 9 (2008), 1369–1398. https://doi.org/10.1145/1390681.1442778 doi: 10.1145/1390681.1442778
[12]	P. Breheny, J. Huang, Coordinate descent algorithms for nonconvex penalized regression with applications to biological feature selection, Ann. Appl. Stat., 5 (2011), 232–253. https://doi.org/10.1214/10-AOAS388 doi: 10.1214/10-AOAS388
[13]	M. Elad, B. Matalon, M. Zibulevsky, Coordinate and subspace optimization methods for linear least squares with non-quadratic regularization, Appl. Comput. Harmonic Anal., 23 (2007), 346–367. https://doi.org/10.1016/j.acha.2007.02.002 doi: 10.1016/j.acha.2007.02.002
[14]	C. Wang, D. Wu, K. Yang, New decentralized positioning schemes for wireless sensor networks based on recursive least-squares optimization, IEEE Wirel. Commun. Lett., 3 (2014), 78–81. https://doi.org/10.1109/WCL.2013.111713.130734 doi: 10.1109/WCL.2013.111713.130734
[15]	J. A. Scott, M. Tuma, Sparse stretching for solving sparse-dense linear least-squares problems, SIAM J. Sci. Comput., 41 (2019), A1604–A1625. https://doi.org/10.1137/18M1181353 doi: 10.1137/18M1181353
[16]	N. J. Higham, Accuracy and Stability of Numerical Algorithms, SIAM, Philadelphia, 2002. https://doi.org/10.2307/2669725
[17]	Y. Saad, Iterative Methods for Sparse Linear Systems, SIAM, Philadelphia, 2003. https://doi.org/10.1137/1.9780898718003.ch4
[18]	T. Strohmer, R. Vershynin, A randomized Kaczmarz algorithm with exponential convergence, J. Fourier Anal. Appl., 15 (2009), 262–278. https://doi.org/10.1007/s00041-008-9030-4 doi: 10.1007/s00041-008-9030-4
[19]	D. Leventhal, A. S. Lewis, Randomized methods for linear constraints: Convergence rates and conditioning, Math. Oper. Res., 35 (2010), 641–654. https://arXiv.org/abs/0806.3015
[20]	Z. S. Lu, L. Xiao, On the complexity analysis of randomized block-coordinate descent methods, J. Math. Program, 152 (2015), 615–642. https://doi.org/10.1007/s10107-014-0800-2 doi: 10.1007/s10107-014-0800-2
[21]	Y. Liu, X. L. Jiang, C. Q. Gu, On maximum residual block and two-step Gauss-Seidel algorithms for linear least-squares problems, Calcolo, 58 (2021), 1–32. https://doi.org/10.1007/s10092-021-00404-x doi: 10.1007/s10092-021-00404-x
[22]	Z. Z. Bai, W. T. Wu, On greedy randomized coordinate descent methods for solving large linear least-squares problems, Numer. Linear Algebra Appl., 26 (2019), 22–37. https://doi.org/10.1002/nla.2237 doi: 10.1002/nla.2237
[23]	J. H. Zhang, J. H. Guo, On relaxed greedy randomized coordinate descent methods for solving large linear least-squares problems, J. Appl. Numer. Math., 157 (2020), 372–384. https://doi.org/10.1016/j.apnum.2020.06.014 doi: 10.1016/j.apnum.2020.06.014
[24]	Z. Z. Bai, L. Wang, W. T. Wu, On convergence rate of the randomized Gauss-Seidel method, Linear Algebra Appl., 611 (2021), 237–252. https://doi.org/10.1016/j.laa.2020.10.028 doi: 10.1016/j.laa.2020.10.028
[25]	J. Nutini, M. Schmidt, I. H. Laradji, M. Friedlander, H. Koepke, Coordinate descent converges faster with the Gauss-Southwell rule than random selection, Int. J. Technol. Manage., 43 (2015), 1632-1641. https://doi.org/10.1504/IJTM.200A019410 doi: 10.1504/IJTM.200A019410
[26]	K. Du, Tight upper bounds for the convergence of the randomized extended Kaczmarz and Gauss-Seidel algorithms, Numer. Linear Algebra Appl., 26 (2019), 22–33. https://doi.org/10.1002/nla.2233 doi: 10.1002/nla.2233
[27]	W. Wu, Paving the Randomized Gauss-Seidel Method, BSc Thesis, Scripps College, Claremont, California, 2017. https://scholarship.claremont.edu/scripps_theses/1074
[28]	D. Needell, R. Ward, Two-subspace projection method for coherent overdetermined systems, J. J. Fourier Anal. Appl., 19 (2013), 256–269. https://doi.org/10.1007/s00041-012-9248-z doi: 10.1007/s00041-012-9248-z
[29]	W. T. Wu, On two-subspace randomized extended Kaczmarz method for solving large linear least-squares problems, Numer. Algor., 89 (2022), 1–31. https://doi.org/10.1007/s11075-021-01104-x doi: 10.1007/s11075-021-01104-x
[30]	Z. Z. Bai, W. T. Wu, On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems, Linear Algebra Appl., 578 (2019), 225–250. https://doi.org/10.1016/j.laa.2019.05.005 doi: 10.1016/j.laa.2019.05.005
[31]	T. A. Davis, Y. Hu, The university of florida sparse matrix collection, ACM Trans. Math. Software, 38 (2011), 1–25. https://doi.org/10.1145/2049662.2049663 doi: 10.1145/2049662.2049663
[32]	P. C. Hansen, Regularization Tools: A Matlab package for analysis and solution of discrete ill-posed problems, Numer. Algor., 06 (1994), 1–35. https://doi.org/10.1007/BF02149761 doi: 10.1007/BF02149761

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)