On the convergence analysis of the greedy randomized Kaczmarz method

On the convergence analysis of the greedy randomized Kaczmarz method | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article On the convergence analysis of the greedy randomized Kaczmarz method Yansheng Su, Deren Han, Yun Zeng, Jiaxin Xie This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-7728326/v1 This work is licensed under a CC BY 4.0 License Status: Published Journal Publication published 09 Mar, 2026 Read the published version in Numerical Algorithms → Version 1 posted 9 You are reading this latest preprint version Abstract In this paper, we analyze the greedy randomized Kaczmarz (GRK) method proposed in Bai and Wu (SIAM J. Sci. Comput., 40(1):A592--A606, 2018) for solving linear systems. We develop tighter greedy probability criteria to effectively select the working row from the coefficient matrix. Notably, we prove that the linear convergence of the GRK method is deterministic and demonstrate that using a tighter threshold parameter can lead to a better convergence factor. Our result revises existing convergence analyses, which are solely based on the expected error by realizing that the iterates of the GRK method are random variables. Consequently, we obtain an improved iteration complexity for the GRK method. Moreover, the Polyak's heavy ball momentum technique is incorporated to improve the performance of the GRK method. We propose a refined convergence analysis, compared with the technique used in Loizou and Richt'{a}rik (Comput. Optim. Appl., 77(3):653--710, 2020), of momentum variants of randomized iterative methods, which shows that the proposed GRK method with momentum (mGRK) also enjoys a deterministic linear convergence. Numerical experiments show that the mGRK method is more efficient than the GRK method. linear systems Kaczmarz greedy probability criterion heavy ball momentum deterministic linear convergence iteration complexity Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Published Journal Publication published 09 Mar, 2026 Read the published version in Numerical Algorithms → Version 1 posted Editorial decision: Revision requested 04 Dec, 2025 Reviews received at journal 04 Dec, 2025 Reviews received at journal 06 Nov, 2025 Reviewers agreed at journal 06 Oct, 2025 Reviewers agreed at journal 05 Oct, 2025 Reviewers invited by journal 05 Oct, 2025 Editor assigned by journal 29 Sep, 2025 Submission checks completed at journal 29 Sep, 2025 First submitted to journal 27 Sep, 2025 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-7728326","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":530247932,"identity":"263d612c-1feb-4ea0-898e-9e66c8f9a5b3","order_by":0,"name":"Yansheng Su","email":"","orcid":"","institution":"Beihang University","correspondingAuthor":false,"prefix":"","firstName":"Yansheng","middleName":"","lastName":"Su","suffix":""},{"id":530247934,"identity":"2f25de31-4f4d-453f-bb03-ba40b12ede49","order_by":1,"name":"Deren Han","email":"","orcid":"","institution":"Beihang University","correspondingAuthor":false,"prefix":"","firstName":"Deren","middleName":"","lastName":"Han","suffix":""},{"id":530247938,"identity":"5c0c454c-3eb9-46d3-9975-6002d06b2ea5","order_by":2,"name":"Yun Zeng","email":"","orcid":"","institution":"Beihang University","correspondingAuthor":false,"prefix":"","firstName":"Yun","middleName":"","lastName":"Zeng","suffix":""},{"id":530247939,"identity":"8e2d3717-8de5-4c9b-bf7c-1da1309abf84","order_by":3,"name":"Jiaxin Xie","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA0ElEQVRIiWNgGAWjYDACZgYGA4aKAxAOD/FazpCkBQQY20jRYnCc+UAx77w7if3tBxgfvG1jkDcnpEWymS3BcOa2Z4kzziQwG85tYzDc2UBACz8zj4HBx22HExsOJLBJ87YxJBgcIKCFjZn/g0HinMOJ888/YP9NlBagLQwGHxsOJ264kcDGTJQWoF8MDGcce2a88cbDZsk55yQMNxDSYnD+8DNjnpo7svPOJx/88KbMRp6gLSDvGEBoxgYgIUFYPRAwPyBK2SgYBaNgFIxcAABH0UGILHqVLQAAAABJRU5ErkJggg==","orcid":"","institution":"Beihang University","correspondingAuthor":true,"prefix":"","firstName":"Jiaxin","middleName":"","lastName":"Xie","suffix":""}],"badges":[],"createdAt":"2025-09-27 12:08:31","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-7728326/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-7728326/v1","draftVersion":[],"editorialEvents":[{"content":"https://doi.org/10.1007/s11075-026-02352-5","type":"published","date":"2026-03-09T15:59:07+00:00"}],"editorialNote":"","failedWorkflow":false,"files":[{"id":93694338,"identity":"ee07ffa8-f355-4a81-9cfb-ec2732cafb67","added_by":"auto","created_at":"2025-10-16 14:28:33","extension":"json","order_by":0,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":5188,"visible":true,"origin":"","legend":"","description":"","filename":"7b8b5d4778c540f19f72479a9dfe427c.json","url":"https://assets-eu.researchsquare.com/files/rs-7728326/v1/636e4c20bfcb0d456616c882.json"},{"id":93694350,"identity":"b4c180a8-b2c1-4f1e-951e-7b6920ed71e2","added_by":"auto","created_at":"2025-10-16 14:28:39","extension":"eps","order_by":1,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":96147,"visible":true,"origin":"","legend":"","description":"","filename":"100001000100010.eps","url":"https://assets-eu.researchsquare.com/files/rs-7728326/v1/c1285c8e9843bdf595f3c754.eps"},{"id":93694352,"identity":"a9defcba-dbc0-4bd0-ae96-fd2f9ab8ad92","added_by":"auto","created_at":"2025-10-16 14:28:44","extension":"eps","order_by":2,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":95147,"visible":true,"origin":"","legend":"","description":"","filename":"10000100050010.eps","url":"https://assets-eu.researchsquare.com/files/rs-7728326/v1/090468415fa65060f7ae64ac.eps"},{"id":93694349,"identity":"44733935-374f-4673-aaf8-cbe97157f826","added_by":"auto","created_at":"2025-10-16 14:28:37","extension":"eps","order_by":3,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":45875,"visible":true,"origin":"","legend":"","description":"","filename":"CPUn100r10040.eps","url":"https://assets-eu.researchsquare.com/files/rs-7728326/v1/c029a36241355535b007629b.eps"},{"id":93694339,"identity":"fe30a1cb-57cc-47a2-9227-ba93280c5212","added_by":"auto","created_at":"2025-10-16 14:28:33","extension":"eps","order_by":4,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":45676,"visible":true,"origin":"","legend":"","description":"","filename":"CPUn100r100.eps","url":"https://assets-eu.researchsquare.com/files/rs-7728326/v1/bd83cf1aad05d8794cf5e7e2.eps"},{"id":93694348,"identity":"a18213c0-6edd-4777-aeb8-7dc52e8a4b1e","added_by":"auto","created_at":"2025-10-16 14:28:35","extension":"eps","order_by":5,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":44922,"visible":true,"origin":"","legend":"","description":"","filename":"CPUn100r9040.eps","url":"https://assets-eu.researchsquare.com/files/rs-7728326/v1/07bdc4284915acbef68e7534.eps"},{"id":93694351,"identity":"56615c7f-4a1a-40e0-b2c6-de9bd1022248","added_by":"auto","created_at":"2025-10-16 14:28:40","extension":"eps","order_by":6,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":45771,"visible":true,"origin":"","legend":"","description":"","filename":"CPUn100r90.eps","url":"https://assets-eu.researchsquare.com/files/rs-7728326/v1/4074dc6d912649848d88fc01.eps"},{"id":93694343,"identity":"e1678df7-af71-46ed-b0dd-a255a0f49795","added_by":"auto","created_at":"2025-10-16 14:28:33","extension":"pdf","order_by":7,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":671709,"visible":true,"origin":"","legend":"","description":"","filename":"DGRKsubmit.pdf","url":"https://assets-eu.researchsquare.com/files/rs-7728326/v1/a13549f87ee2cddc3f1a8efd.pdf"},{"id":93694340,"identity":"fa0849db-4f98-4d26-b1a6-00dd89c28e60","added_by":"auto","created_at":"2025-10-16 14:28:33","extension":"pdf","order_by":8,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":50181,"visible":true,"origin":"","legend":"","description":"","filename":"NAcoverletter.pdf","url":"https://assets-eu.researchsquare.com/files/rs-7728326/v1/3da06ace4a01c15a6e329d07.pdf"},{"id":93694890,"identity":"91f1b88f-4d82-4838-bb3f-2b398f6bc005","added_by":"auto","created_at":"2025-10-16 14:36:33","extension":"eps","order_by":9,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":91528,"visible":true,"origin":"","legend":"","description":"","filename":"WorldCities.eps","url":"https://assets-eu.researchsquare.com/files/rs-7728326/v1/40701d54b3461f805c91c4b1.eps"},{"id":93694342,"identity":"984cb1de-a655-4f98-a119-6f5ce26ad132","added_by":"auto","created_at":"2025-10-16 14:28:33","extension":"eps","order_by":10,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":82441,"visible":true,"origin":"","legend":"","description":"","filename":"crew1.eps","url":"https://assets-eu.researchsquare.com/files/rs-7728326/v1/5a1e396595da513102f38ce8.eps"},{"id":93694889,"identity":"6e0ef318-9c96-45af-8fc4-7ceaac9e8c39","added_by":"auto","created_at":"2025-10-16 14:36:33","extension":"eps","order_by":11,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":58401,"visible":true,"origin":"","legend":"","description":"","filename":"iGRKGRK100.eps","url":"https://assets-eu.researchsquare.com/files/rs-7728326/v1/c3b9b6565dac055ccb78ab54.eps"},{"id":93694344,"identity":"61031c8a-f39c-4772-b658-6e9a580f4302","added_by":"auto","created_at":"2025-10-16 14:28:33","extension":"eps","order_by":12,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":58395,"visible":true,"origin":"","legend":"","description":"","filename":"iGRKGRK90.eps","url":"https://assets-eu.researchsquare.com/files/rs-7728326/v1/2b6082c712d56360a1b0a050.eps"},{"id":93694407,"identity":"61aedcca-0ae6-48ae-adb4-c8e2bb9ad477","added_by":"auto","created_at":"2025-10-16 14:28:57","extension":"cls","order_by":13,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":55332,"visible":true,"origin":"","legend":"","description":"","filename":"snjnl.cls","url":"https://assets-eu.researchsquare.com/files/rs-7728326/v1/b44c947605e25d7d906bb79c.cls"},{"id":93694341,"identity":"f52b9dbf-218a-493b-907e-d807580b2649","added_by":"auto","created_at":"2025-10-16 14:28:33","extension":"bst","order_by":14,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":64141,"visible":true,"origin":"","legend":"","description":"","filename":"snmathphysnum.bst","url":"https://assets-eu.researchsquare.com/files/rs-7728326/v1/ade6cf86c8a15097492c6d0d.bst"},{"id":93694345,"identity":"fd7d7aa9-9609-461d-87f9-a9304e79a26a","added_by":"auto","created_at":"2025-10-16 14:28:33","extension":"xml","order_by":15,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":101226,"visible":true,"origin":"","legend":"","description":"","filename":"7b8b5d4778c540f19f72479a9dfe427c1structuring.xml","url":"https://assets-eu.researchsquare.com/files/rs-7728326/v1/a937306db0bfc583d087eb97.xml"},{"id":104740254,"identity":"ff2b0aea-9da6-4c80-b487-527a8237f91a","added_by":"auto","created_at":"2026-03-16 16:16:16","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":573723,"visible":true,"origin":"","legend":"","description":"","filename":"DGRKsubmit.pdf","url":"https://assets-eu.researchsquare.com/files/rs-7728326/v1_covered_9d427481-3e36-43c2-95b0-926dcf9c1656.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"On the convergence analysis of the greedy randomized Kaczmarz method","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":true,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"numerical-algorithms","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"numa","sideBox":"Learn more about [Numerical Algorithms](http://link.springer.com/journal/11075)","snPcode":"11075","submissionUrl":"https://submission.nature.com/new-submission/11075/3","title":"Numerical Algorithms","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"linear systems, Kaczmarz, greedy probability criterion, heavy ball momentum, deterministic linear convergence, iteration complexity","lastPublishedDoi":"10.21203/rs.3.rs-7728326/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-7728326/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"In this paper, we analyze the greedy randomized Kaczmarz (GRK) method proposed in Bai and Wu (SIAM J. Sci. Comput., 40(1):A592--A606, 2018) for solving linear systems. We develop tighter greedy probability criteria to effectively select the working row from the coefficient matrix. Notably, we prove that the linear convergence of the GRK method is deterministic and demonstrate that using a tighter threshold parameter can lead to a better convergence factor. Our result revises existing convergence analyses, which are solely based on the expected error by realizing that the iterates of the GRK method are random variables. Consequently, we obtain an improved iteration complexity for the GRK method. \nMoreover, the Polyak's heavy ball momentum technique is incorporated to improve the performance of the GRK method. We propose a refined convergence analysis, compared with the technique used in Loizou and Richt\\'{a}rik (Comput. Optim. Appl., 77(3):653--710, 2020), of momentum variants of randomized iterative methods, which shows that the proposed GRK method with momentum (mGRK) also enjoys a deterministic linear convergence. Numerical experiments show that the mGRK method is more efficient than the GRK method.","manuscriptTitle":"On the convergence analysis of the greedy randomized Kaczmarz method","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-10-16 14:28:28","doi":"10.21203/rs.3.rs-7728326/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2025-12-04T15:06:58+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2025-12-04T11:52:53+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2025-11-07T01:05:26+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"119152900630179871392830148120218325402","date":"2025-10-06T10:07:07+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"158351786515848457032230376092584171577","date":"2025-10-05T23:55:00+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2025-10-05T19:17:43+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2025-09-29T08:24:53+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2025-09-29T04:21:48+00:00","index":"","fulltext":""},{"type":"submitted","content":"Numerical Algorithms","date":"2025-09-27T12:01:25+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"numerical-algorithms","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"numa","sideBox":"Learn more about [Numerical Algorithms](http://link.springer.com/journal/11075)","snPcode":"11075","submissionUrl":"https://submission.nature.com/new-submission/11075/3","title":"Numerical Algorithms","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"a7745ade-d3f9-42ce-9332-ce86755e7568","owner":[],"postedDate":"October 16th, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"published-in-journal","subjectAreas":[],"tags":[],"updatedAt":"2026-03-16T16:08:39+00:00","versionOfRecord":{"articleIdentity":"rs-7728326","link":"https://doi.org/10.1007/s11075-026-02352-5","journal":{"identity":"numerical-algorithms","isVorOnly":false,"title":"Numerical Algorithms"},"publishedOn":"2026-03-09 15:59:07","publishedOnDateReadable":"March 9th, 2026"},"versionCreatedAt":"2025-10-16 14:28:28","video":"","vorDoi":"10.1007/s11075-026-02352-5","vorDoiUrl":"https://doi.org/10.1007/s11075-026-02352-5","workflowStages":[]},"version":"v1","identity":"rs-7728326","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-7728326","identity":"rs-7728326","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}