{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,21]],"date-time":"2024-12-21T05:09:27Z","timestamp":1734757767599,"version":"3.32.0"},"reference-count":23,"publisher":"American Institute of Mathematical Sciences (AIMS)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["NHM"],"published-print":{"date-parts":[[2024]]},"abstract":"<jats:p xml:lang=\"fr\">&lt;p&gt;In this paper, for solving linear feasibility problems we propose two randomized methods: a multiple row-action method (RMR) based on partial rows of residual vectors and its generalized method (GRMR) with history information in updating the current update. By introducing a linear combination of the information from the previous and subsequent iterative steps with the relaxation parameter $ \\xi $, the GRMR method unifies various RMR-type algorithms. A thorough convergence analysis for the proposed methods is provided. The theoretical results show the theoretical convergence rate of the GRMR method with $ 0\\leq \\xi\\leq1 $ is always worse or equal compared to that of the RMR method. Therefore, a global linear rate for the GRMR method is explored for $ -1\\leq \\xi\\leq 0 $. Finally, numerical experiments on both randomly generated and real-world data show our algorithms outperform the original methods in terms of computing time and iteration counts. In particular, when the appropriate parameters are selected, the GRMR method is the competitive row-action method for solving linear feasibility problems.&lt;\/p&gt;<\/jats:p>","DOI":"10.3934\/nhm.2024062","type":"journal-article","created":{"date-parts":[[2024,12,18]],"date-time":"2024-12-18T10:11:21Z","timestamp":1734516681000},"page":"1448-1469","source":"Crossref","is-referenced-by-count":0,"title":["On randomized multiple row-action methods for linear feasibility problems"],"prefix":"10.3934","volume":"19","author":[{"given":"Hui","family":"Song","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wendi","family":"Bao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lili","family":"Xing","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weiguo","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"2321","reference":[{"key":"key-10.3934\/nhm.2024062-1","unstructured":"S. Karczmarz, Angen$\\ddot{a}$herte aufl$\\ddot{o}$sung von systemen linearer gleichungen, <i>Bull. Int. Acad. Polon. Sci. Lett.<\/i>, <b>35<\/b> (1937), 355\u2013357."},{"key":"key-10.3934\/nhm.2024062-2","doi-asserted-by":"publisher","unstructured":"G. Richard, B. Robert, H. T. Gabor, Algebraic Reconstruction Techniques (ART) for three-dimensional electron microscopy and X-ray photography, <i>J. Theor. Biol.<\/i>, <b>29<\/b> (1970), 471\u2013481. https:\/\/doi.org\/10.1016\/0022-5193(70)90109-8","DOI":"10.1016\/0022-5193(70)90109-8"},{"key":"key-10.3934\/nhm.2024062-3","doi-asserted-by":"publisher","unstructured":"T. Strohmer, R. Vershynin, A randomized Kaczmarz algorithm with exponential convergence, <i>J. Fourier Anal. Appl.<\/i>, <b>15<\/b> (2009), 262\u2013278. https:\/\/doi.org\/10.1007\/s00041-008-9030-4","DOI":"10.1007\/s00041-008-9030-4"},{"key":"key-10.3934\/nhm.2024062-4","doi-asserted-by":"publisher","unstructured":"Z. Z. Bai, W. T. Wu, On convergence rate of the randomized Kaczmarz method, <i>Linear Algebra Appl.<\/i>, <b>553<\/b> (2018), 252\u2013269. https:\/\/doi.org\/10.1016\/j.laa.2018.05.009","DOI":"10.1016\/j.laa.2018.05.009"},{"key":"key-10.3934\/nhm.2024062-5","doi-asserted-by":"publisher","unstructured":"Y. C. Eldar, D. Needell, Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma, <i>Numer. Algorithms<\/i>, <b>58<\/b> (2011), 163\u2013177. https:\/\/doi.org\/10.1007\/s11075-011-9451-z","DOI":"10.1007\/s11075-011-9451-z"},{"key":"key-10.3934\/nhm.2024062-6","unstructured":"J. H. Guo, W. G. Li, The randomized Kaczmarz method with a new random selection rule, <i>Numer. Math. J. Chin. Univ.<\/i>, <b>40<\/b> (2018), 65\u201375."},{"key":"key-10.3934\/nhm.2024062-7","doi-asserted-by":"publisher","unstructured":"J. J. Zhang, A new greedy Kaczmarz algorithm for the solution of very large linear systems, <i>Appl. Math. Lett.<\/i>, <b>91<\/b> (2019), 207\u2013212. https:\/\/doi.org\/10.1016\/j.aml.2018.12.022","DOI":"10.1016\/j.aml.2018.12.022"},{"key":"key-10.3934\/nhm.2024062-8","doi-asserted-by":"publisher","unstructured":"Y. Liu, C. Q. Gu, Variant of greedy randomized Kaczmarz for ridge regression, <i>Appl. Numer. Math.<\/i>, <b>143<\/b> (2019), 223\u2013246. https:\/\/doi.org\/10.1016\/j.apnum.2019.04.008","DOI":"10.1016\/j.apnum.2019.04.008"},{"key":"key-10.3934\/nhm.2024062-9","doi-asserted-by":"publisher","unstructured":"T. Elfving, Block-iterative methods for consistent and inconsistent linear equations, <i>Numer. Math.<\/i>, <b>35<\/b> (1980), 1\u201312. https:\/\/doi.org\/10.1007\/BF01396365","DOI":"10.1007\/BF01396365"},{"key":"key-10.3934\/nhm.2024062-10","doi-asserted-by":"publisher","unstructured":"D. Needell, J. A. Tropp, Paved with good intentions: Analysis of a randomized block Kaczmarz method, <i>Linear Algebra Appl.<\/i>, <b>441<\/b> (2014), 199\u2013221. https:\/\/doi.org\/10.1016\/j.laa.2012.12.022","DOI":"10.1016\/j.laa.2012.12.022"},{"key":"key-10.3934\/nhm.2024062-11","doi-asserted-by":"publisher","unstructured":"R. M. Gower, P. Richt\u00e1rik, Randomized iterative methods for linear systems, <i>SIAM J. Matrix Anal. Appl.<\/i>, <b>36<\/b> (2015), 1660\u20131690. https:\/\/doi.org\/10.1137\/15M1025487","DOI":"10.1137\/15M1025487"},{"key":"key-10.3934\/nhm.2024062-12","doi-asserted-by":"publisher","unstructured":"J. Q. Chen, Z. D. Huang, On a fast deterministic block Kaczmarz method for solving large-scale linear systems, <i>Numer. Algorithms<\/i>, <b>89<\/b> (2022), 1007\u20131029. https:\/\/doi.org\/10.1007\/s11075-021-01143-4","DOI":"10.1007\/s11075-021-01143-4"},{"key":"key-10.3934\/nhm.2024062-13","doi-asserted-by":"publisher","unstructured":"Z. Z. Bai, W. T. Wu, On greedy randomized Kaczmarz method for solving large sparse linear systems, <i>SIAM J. Sci. Comput.<\/i>, <b>40<\/b> (2018), A592\u2013A606. https:\/\/doi.org\/10.1137\/17M1137747","DOI":"10.1137\/17M1137747"},{"key":"key-10.3934\/nhm.2024062-14","doi-asserted-by":"publisher","unstructured":"N. C. Wu, L. X. Cui, Q. Zuo, On the relaxed greedy deterministic row and column iterative methods, <i>Appl. Math. Comput.<\/i>, <b>432<\/b> (2022), 127339. https:\/\/doi.org\/10.1016\/j.amc.2022.127339","DOI":"10.1016\/j.amc.2022.127339"},{"key":"key-10.3934\/nhm.2024062-15","unstructured":"S. Yousef, <i>Iterative Methods for Sparse Linear Systems<\/i>, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2003."},{"key":"key-10.3934\/nhm.2024062-16","doi-asserted-by":"publisher","unstructured":"D. Leventhal, A. S. Lewis, Randomized methods for linear constraints: Convergence rates and conditioning, <i>Math. Oper. Res.<\/i>, <b>35<\/b> (2010), 641\u2013654. https:\/\/doi.org\/10.1287\/moor.1100.0456","DOI":"10.1287\/moor.1100.0456"},{"key":"key-10.3934\/nhm.2024062-17","doi-asserted-by":"publisher","unstructured":"S. Agmon, The relaxation method for linear inequalities, <i>Can. J. Math.<\/i>, <b>6<\/b> (1954), 382\u2013392. https:\/\/doi.org\/10.4153\/CJM-1954-037-2","DOI":"10.4153\/CJM-1954-037-2"},{"key":"key-10.3934\/nhm.2024062-18","doi-asserted-by":"publisher","unstructured":"T. S. Motzkin, I. J. Schoenberg, The relaxation method for linear inequalities, <i>Can. J. Math.<\/i>, <b>6<\/b> (1954), 393\u2013404. https:\/\/doi.org\/10.4153\/CJM-1954-038-x","DOI":"10.4153\/CJM-1954-038-x"},{"key":"key-10.3934\/nhm.2024062-19","doi-asserted-by":"publisher","unstructured":"J. A. De Loera, J. Haddock, D. Needell, A sampling Kaczmarz-Motzkin algorithm for linear feasibility, <i>SIAM J. Sci. Comput.<\/i>, <b>39<\/b> (2017), S66\u2013S87. https:\/\/doi.org\/10.1137\/16M1073807","DOI":"10.1137\/16M1073807"},{"key":"key-10.3934\/nhm.2024062-20","doi-asserted-by":"publisher","unstructured":"M. S. Morshed, M. S. Islam, M. Noor-E-Alam, Sampling Kaczmarz-Motzkin method for linear feasibility problems: Generalization and acceleration, <i>Math. Program.<\/i>, <b>194<\/b> (2022), 719\u2013779. https:\/\/doi.org\/10.1007\/s10107-021-01649-8","DOI":"10.1007\/s10107-021-01649-8"},{"key":"key-10.3934\/nhm.2024062-21","doi-asserted-by":"publisher","unstructured":"D. Leventhal, A. S. Lewis, Randomized methods for linear constraints: Convergence rates and conditioning, <i>Math. Oper. Res.<\/i>, <b>35<\/b> (2010), 641\u2013654. https:\/\/doi.org\/10.1287\/moor.1100.0456","DOI":"10.1287\/moor.1100.0456"},{"key":"key-10.3934\/nhm.2024062-22","doi-asserted-by":"crossref","unstructured":"A. J. Hoffman, On approximate solutions of systems of linear inequalities, <i>J. Res. Nat. Bur. Stand.<\/i>, <b>49<\/b> (1952), 263\u2013265.","DOI":"10.6028\/jres.049.027"},{"key":"key-10.3934\/nhm.2024062-23","doi-asserted-by":"publisher","unstructured":"S. P. Kolodziej, A. Mohsen, B Matthew, D. Jarrett, A. D. Timothy, H. Matthew, et al., The SuiteSparse matrix collection website interface, <i>J. Open Source Software<\/i>, <b>4<\/b> (2019), 1244. https:\/\/doi.org\/10.21105\/joss.01244","DOI":"10.21105\/joss.01244"}],"container-title":["Networks and Heterogeneous Media"],"original-title":[],"link":[{"URL":"http:\/\/www.aimspress.com\/article\/doi\/10.3934\/nhm.2024062?viewType=html","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,20]],"date-time":"2024-12-20T05:39:13Z","timestamp":1734673153000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.aimspress.com\/article\/doi\/10.3934\/nhm.2024062"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024]]}},"URL":"https:\/\/doi.org\/10.3934\/nhm.2024062","relation":{},"ISSN":["1556-1801"],"issn-type":[{"type":"print","value":"1556-1801"}],"subject":[],"published":{"date-parts":[[2024]]}}}