{"id":2019,"date":"2025-06-16T14:04:00","date_gmt":"2025-06-16T14:04:00","guid":{"rendered":"https:\/\/www.ethanepperly.com\/?p=2019"},"modified":"2025-06-16T21:34:35","modified_gmt":"2025-06-16T21:34:35","slug":"randomized-kaczmarz-how-should-you-sample","status":"publish","type":"post","link":"https:\/\/www.ethanepperly.com\/index.php\/2025\/06\/16\/randomized-kaczmarz-how-should-you-sample\/","title":{"rendered":"Randomized Kaczmarz: How Should You Sample?"},"content":{"rendered":"\n<p>The <a href=\"https:\/\/www.math.ucdavis.edu\/~strohmer\/courses\/270\/kaczmarz_randomized.pdf\">randomized Kaczmarz method<\/a> is a method for solving <a href=\"https:\/\/en.wikipedia.org\/wiki\/System_of_linear_equations\">systems of linear equations<\/a>:<p class=\"ql-center-displayed-equation\" style=\"line-height: 14px;\"><span class=\"ql-right-eqno\"> (1) <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-29d9a4727a905120c7e471f5f6d88048_l3.png\" height=\"14\" width=\"195\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#116;&#101;&#120;&#116;&#123;&#70;&#105;&#110;&#100;&#32;&#36;&#120;&#36;&#32;&#115;&#117;&#99;&#104;&#32;&#116;&#104;&#97;&#116;&#32;&#125;&#32;&#65;&#120;&#32;&#61;&#32;&#98;&#46;&#32;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>Throughout this post, the matrix <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-11f4f587954b361e7d78940f65b8d70d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"13\" style=\"vertical-align: 0px;\"\/> will have dimensions <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-97cff47e97f2cf28bbd3efb3b22a37bd_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#110;&#92;&#116;&#105;&#109;&#101;&#115;&#32;&#100;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"42\" style=\"vertical-align: 0px;\"\/>. Beginning from an initial iterate <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-582b045cb1264dacb4c6888a6b5114fe_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;&#95;&#48;&#32;&#61;&#32;&#48;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"50\" style=\"vertical-align: -3px;\"\/>, randomized Kaczmarz works as follows. For <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-d6f6f964d166c069b5c3c658646d800c_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#116;&#32;&#61;&#32;&#48;&#44;&#49;&#44;&#50;&#44;&#92;&#108;&#100;&#111;&#116;&#115;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"100\" style=\"vertical-align: -4px;\"\/>:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Sample a random row index <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-cd51bc9af5abfa93527fa3adce74a62d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#105;&#95;&#116;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"11\" style=\"vertical-align: -3px;\"\/> with probability <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-5f9b03c95a8be0c1afbdf024a1991454_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#112;&#114;&#111;&#98;&#32;&#92;&#123;&#32;&#105;&#95;&#116;&#32;&#61;&#32;&#106;&#32;&#92;&#125;&#32;&#61;&#32;&#112;&#95;&#106;\" title=\"Rendered by QuickLaTeX.com\" height=\"20\" width=\"111\" style=\"vertical-align: -6px;\"\/>.<\/li>\n\n\n\n<li>Update to enforce the equation <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-6fc84f2cccf0d4d9ed167b0a698cfb3f_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#97;&#95;&#123;&#105;&#95;&#116;&#125;&#94;&#92;&#116;&#111;&#112;&#32;&#120;&#32;&#61;&#32;&#98;&#95;&#123;&#105;&#95;&#116;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"22\" width=\"72\" style=\"vertical-align: -7px;\"\/> holds exactly: <p class=\"ql-center-displayed-equation\" style=\"line-height: 49px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-99cc99e6de2ca367d24ee6f20e610735_l3.png\" height=\"49\" width=\"203\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#120;&#95;&#123;&#116;&#43;&#49;&#125;&#32;&#92;&#99;&#111;&#108;&#111;&#110;&#101;&#113;&#113;&#32;&#120;&#95;&#116;&#32;&#43;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#98;&#95;&#123;&#105;&#95;&#116;&#125;&#32;&#45;&#32;&#97;&#95;&#123;&#105;&#95;&#116;&#125;&#94;&#92;&#116;&#111;&#112;&#32;&#120;&#95;&#116;&#125;&#123;&#92;&#110;&#111;&#114;&#109;&#123;&#97;&#95;&#123;&#105;&#95;&#116;&#125;&#125;&#94;&#50;&#125;&#32;&#97;&#95;&#123;&#105;&#95;&#116;&#125;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>Throughout this post, <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-208dceb2eaa2dd0d1b1242226407ab04_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#97;&#95;&#106;&#94;&#92;&#116;&#111;&#112;\" title=\"Rendered by QuickLaTeX.com\" height=\"23\" width=\"19\" style=\"vertical-align: -8px;\"\/> denotes the <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-fe087f8cefab0bcb3270609914ada26c_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#106;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"9\" style=\"vertical-align: -4px;\"\/>th row of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-11f4f587954b361e7d78940f65b8d70d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"13\" style=\"vertical-align: 0px;\"\/>.<\/li>\n<\/ul>\n\n\n\n<p>What selection probabilities <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-7ef5f113a5b8fe18ca8721ab8c07b90d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#112;&#95;&#106;\" title=\"Rendered by QuickLaTeX.com\" height=\"14\" width=\"16\" style=\"vertical-align: -6px;\"\/> should we use? The answer to this question may depend on whether the system (1) is <a href=\"https:\/\/en.wikipedia.org\/wiki\/System_of_linear_equations#Consistency\">consistent<\/a>, i.e., whether it possesses a solution <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-b312d649591164b7149ed0756f694a76_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"10\" style=\"vertical-align: 0px;\"\/>. <em><mark style=\"background-color:#fff4d7\" class=\"has-inline-color\">For this post, we assume (1) is consistent<\/mark><\/em>; see <a href=\"https:\/\/www.ethanepperly.com\/index.php\/2024\/12\/02\/randomized-kaczmarz-is-asympotically-unbiased-for-least-squares\/\">this previous post<\/a> for a discussion of the inconsistent case.<\/p>\n\n\n\n<p>The classical selection probabilities for randomized Kaczmarz were proposed by <a href=\"https:\/\/www.math.ucdavis.edu\/~strohmer\/\">Strohmer<\/a> and <a href=\"https:\/\/www.math.uci.edu\/~rvershyn\/\">Vershynin<\/a> in <a href=\"https:\/\/www.math.ucdavis.edu\/~strohmer\/courses\/270\/kaczmarz_randomized.pdf\">their seminal paper<\/a>: <p class=\"ql-center-displayed-equation\" style=\"line-height: 49px;\"><span class=\"ql-right-eqno\"> (1) <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-c0282178b77487afd710ad66bb50707b_l3.png\" height=\"49\" width=\"244\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#112;&#95;&#106;&#32;&#61;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#92;&#110;&#111;&#114;&#109;&#123;&#97;&#95;&#106;&#125;&#94;&#50;&#125;&#123;&#92;&#110;&#111;&#114;&#109;&#123;&#65;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#125;&#32;&#92;&#113;&#117;&#97;&#100;&#32;&#92;&#116;&#101;&#120;&#116;&#123;&#102;&#111;&#114;&#32;&#125;&#32;&#106;&#32;&#61;&#32;&#49;&#44;&#50;&#44;&#92;&#108;&#100;&#111;&#116;&#115;&#44;&#110;&#46;&#32;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>Computing these selection probabilities requires a full pass over the matrix, which can be expensive for the largest problems.<sup class=\"modern-footnotes-footnote \" data-mfn=\"1\" data-mfn-post-scope=\"000000000000057e0000000000000000_2019\"><a href=\"javascript:void(0)\"  role=\"button\" aria-pressed=\"false\" aria-describedby=\"mfn-content-000000000000057e0000000000000000_2019-1\">1<\/a><\/sup><span id=\"mfn-content-000000000000057e0000000000000000_2019-1\" role=\"tooltip\" class=\"modern-footnotes-footnote__note\" tabindex=\"0\" data-mfn=\"1\">This initial pass <a href=\"https:\/\/www.ethanepperly.com\/index.php\/2024\/10\/08\/rejection-sampling\/#motivating-application-randomized-kaczmarz\">can sometimes be avoided by using rejection sampling<\/a>, though.<\/span> A computationally appealing alternative is to implement randomized Kaczmarz with uniform selection probabilities <p class=\"ql-center-displayed-equation\" style=\"line-height: 36px;\"><span class=\"ql-right-eqno\"> (2) <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-b0a9325d8b121aaab8d4547fa378ffed_l3.png\" height=\"36\" width=\"212\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#112;&#95;&#106;&#32;&#61;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#49;&#125;&#123;&#110;&#125;&#32;&#92;&#113;&#117;&#97;&#100;&#32;&#92;&#116;&#101;&#120;&#116;&#123;&#102;&#111;&#114;&#32;&#125;&#32;&#106;&#32;&#61;&#32;&#49;&#44;&#50;&#44;&#92;&#108;&#100;&#111;&#116;&#115;&#44;&#110;&#46;&#32;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>Ignoring computational cost, which sampling rule leads to faster convergence: (1) or (2)?<\/p>\n\n\n\n<p>Surprisingly, to me at least, the simpler strategy (2) often works better than (1). Here is a simple example. Define a matrix <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-4eda57d46ba662a0cb2b0adbf9d30325_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;&#32;&#92;&#105;&#110;&#32;&#92;&#114;&#101;&#97;&#108;&#94;&#123;&#50;&#48;&#92;&#116;&#105;&#109;&#101;&#115;&#32;&#50;&#48;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"87\" style=\"vertical-align: -1px;\"\/> with entries <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-5274101325585edde5fe813722fd902b_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;&#95;&#123;&#105;&#106;&#125;&#32;&#61;&#32;&#92;&#109;&#105;&#110;&#40;&#105;&#44;&#106;&#41;&#94;&#50;\" title=\"Rendered by QuickLaTeX.com\" height=\"21\" width=\"121\" style=\"vertical-align: -6px;\"\/>, and choose the right-hand side <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-9eada64951f0c411314341662921f7d6_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#98;&#92;&#105;&#110;&#92;&#114;&#101;&#97;&#108;&#94;&#123;&#50;&#48;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"56\" style=\"vertical-align: -1px;\"\/> with standard Gaussian random entries. The convergence of standard RK with sampling rule (1) and uniform RK with sampling rule (2) is shown in the plot below. After a million iterations, the difference in final accuracy is dramatic: the final relative error 0.00012 was uniform RK and 0.67 for standard RK!<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"765\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/uploads\/2024\/12\/scaling_example-1024x765.png\" alt=\"Error for randomized Kaczmarz with both squared row norm sampling (&quot;standard&quot;) and uniformly random rows on matrix with entries min(i,j)^2. Uniform randomized Kaczmarz achieves significantly smaller final error\" class=\"wp-image-2020\" srcset=\"https:\/\/www.ethanepperly.com\/wp-content\/uploads\/2024\/12\/scaling_example-1024x765.png 1024w, https:\/\/www.ethanepperly.com\/wp-content\/uploads\/2024\/12\/scaling_example-300x224.png 300w, https:\/\/www.ethanepperly.com\/wp-content\/uploads\/2024\/12\/scaling_example-768x573.png 768w, https:\/\/www.ethanepperly.com\/wp-content\/uploads\/2024\/12\/scaling_example-1536x1147.png 1536w, https:\/\/www.ethanepperly.com\/wp-content\/uploads\/2024\/12\/scaling_example.png 1784w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure><\/div>\n\n\n<p>In fairness, uniform RK does not always outperform standard RK. If we change the matrix entries to <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-3e55599e1ca5db406dec7f13782ee1d5_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;&#95;&#123;&#105;&#106;&#125;&#32;&#61;&#32;&#92;&#109;&#105;&#110;&#40;&#105;&#44;&#106;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"20\" width=\"113\" style=\"vertical-align: -6px;\"\/>, then the performance of both methods is similar, with both methods ending with a relative error of about 0.07.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"765\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/uploads\/2024\/12\/scaling_example_2-1024x765.png\" alt=\"Error for randomized Kaczmarz with both squared row norm sampling (&quot;standard&quot;) and uniformly random rows on matrix with entries min(i,j). Uniform randomized Kaczmarz and standard randomized Kaczmarz achieve comparable final errors\" class=\"wp-image-2021\" srcset=\"https:\/\/www.ethanepperly.com\/wp-content\/uploads\/2024\/12\/scaling_example_2-1024x765.png 1024w, https:\/\/www.ethanepperly.com\/wp-content\/uploads\/2024\/12\/scaling_example_2-300x224.png 300w, https:\/\/www.ethanepperly.com\/wp-content\/uploads\/2024\/12\/scaling_example_2-768x573.png 768w, https:\/\/www.ethanepperly.com\/wp-content\/uploads\/2024\/12\/scaling_example_2-1536x1147.png 1536w, https:\/\/www.ethanepperly.com\/wp-content\/uploads\/2024\/12\/scaling_example_2.png 1784w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure><\/div>\n\n\n<p>Another experiment, presented in <a href=\"https:\/\/ar5iv.org\/html\/math\/0702226#S4.SS1\">section 4.1 of Strohmer and Vershynin&#8217;s original paper<\/a>, provides an example where standard RK converges a bit more than twice as fast as uniform RK (called &#8220;simple RK&#8221; in their paper). Still, taken all together, these experiments demonstrate that standard RK (sampling probabilities (1)) is often not dramatically better than uniform RK (sampling probabilities (2)), and uniform RK can be much better than standard RK.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Randomized Kaczmarz Error Bounds<\/h2>\n\n\n\n<p>Why does uniform RK often outperform standard RK? To answer these questions, let&#8217;s look at the error bounds for the RK method.<\/p>\n\n\n\n<p>The classical analysis of standard RK shows the method is <a href=\"https:\/\/en.wikipedia.org\/wiki\/Rate_of_convergence#Comparing_asymptotic_rates_of_convergence\">geometrically convergent<\/a> <p class=\"ql-center-displayed-equation\" style=\"line-height: 32px;\"><span class=\"ql-right-eqno\"> (3) <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-1f788737bb459ed2beaab020bca517c2_l3.png\" height=\"32\" width=\"321\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#101;&#120;&#112;&#101;&#99;&#116;&#92;&#108;&#101;&#102;&#116;&#091;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#120;&#95;&#116;&#32;&#45;&#32;&#120;&#95;&#92;&#115;&#116;&#97;&#114;&#125;&#94;&#50;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#093;&#32;&#92;&#108;&#101;&#32;&#40;&#49;&#32;&#45;&#32;&#92;&#107;&#97;&#112;&#112;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#100;&#101;&#109;&#125;&#40;&#65;&#41;&#94;&#123;&#45;&#50;&#125;&#41;&#94;&#116;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#120;&#95;&#92;&#115;&#116;&#97;&#114;&#125;&#94;&#50;&#46;&#32;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>Here, <p class=\"ql-center-displayed-equation\" style=\"line-height: 64px;\"><span class=\"ql-right-eqno\"> (4) <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-824557fbf90de5be0f9756f9089728aa_l3.png\" height=\"64\" width=\"322\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#107;&#97;&#112;&#112;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#100;&#101;&#109;&#125;&#40;&#65;&#41;&#32;&#61;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#92;&#110;&#111;&#114;&#109;&#123;&#65;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#125;&#123;&#92;&#115;&#105;&#103;&#109;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#109;&#105;&#110;&#125;&#40;&#65;&#41;&#125;&#32;&#61;&#32;&#92;&#115;&#113;&#114;&#116;&#123;&#92;&#115;&#117;&#109;&#95;&#105;&#32;&#92;&#108;&#101;&#102;&#116;&#40;&#92;&#102;&#114;&#97;&#99;&#123;&#92;&#115;&#105;&#103;&#109;&#97;&#95;&#105;&#40;&#65;&#41;&#125;&#123;&#92;&#115;&#105;&#103;&#109;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#109;&#105;&#110;&#125;&#40;&#65;&#41;&#125;&#92;&#114;&#105;&#103;&#104;&#116;&#41;&#94;&#50;&#125;&#32;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>is known as the <em>Demmel condition number<\/em> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-e39567769250a9534f634a599e021bca_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#115;&#105;&#103;&#109;&#97;&#95;&#105;&#40;&#65;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"42\" style=\"vertical-align: -5px;\"\/> are the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Singular_value_decomposition\">singular values<\/a> of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-11f4f587954b361e7d78940f65b8d70d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"13\" style=\"vertical-align: 0px;\"\/>. Recall that we have assumed the system <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-bb1076898a88ac5d6a1c74d7932dd5fc_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;&#120;&#32;&#61;&#32;&#98;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"55\" style=\"vertical-align: 0px;\"\/> is consistent, possessing a solution <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-4c269341681e03c841aa0aee1e9af79d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;&#95;&#92;&#115;&#116;&#97;&#114;\" title=\"Rendered by QuickLaTeX.com\" height=\"11\" width=\"17\" style=\"vertical-align: -3px;\"\/>. If there are multiple solutions, we let <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-4c269341681e03c841aa0aee1e9af79d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;&#95;&#92;&#115;&#116;&#97;&#114;\" title=\"Rendered by QuickLaTeX.com\" height=\"11\" width=\"17\" style=\"vertical-align: -3px;\"\/> denote the solution of <a href=\"https:\/\/en.wikipedia.org\/wiki\/Moore\u2013Penrose_inverse#Minimum_norm_solution_to_a_linear_system\">minimum norm<\/a>.<\/p>\n\n\n\n<p>What about uniform RK? Let <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-36195eb783f50b055062c622877d898e_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#68;&#95;&#65;&#32;&#61;&#32;&#92;&#100;&#105;&#97;&#103;&#32;&#40;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#97;&#95;&#105;&#125;&#94;&#123;&#45;&#49;&#125;&#32;&#58;&#32;&#105;&#61;&#49;&#44;&#92;&#108;&#100;&#111;&#116;&#115;&#44;&#110;&#32;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"22\" width=\"217\" style=\"vertical-align: -5px;\"\/> denote a diagonal matrix containing the inverse row norms, and introduce the <em>row-equilibrated matrix<\/em> <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-66c052278030d640588fb806f24d1a47_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#68;&#95;&#65;&#32;&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"39\" style=\"vertical-align: -3px;\"\/>. The row-equilibrated matrix <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-66c052278030d640588fb806f24d1a47_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#68;&#95;&#65;&#32;&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"39\" style=\"vertical-align: -3px;\"\/> has been obtained from <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-11f4f587954b361e7d78940f65b8d70d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"13\" style=\"vertical-align: 0px;\"\/> by rescaling each of its rows to have unit norm.<\/p>\n\n\n\n<p>Uniform RK can then be related to standard RK run on the row-equilibrated matrix:<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p><strong>Fact (uniform sampling and row equilibration):<\/strong> Uniform RK on the system <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-bb1076898a88ac5d6a1c74d7932dd5fc_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;&#120;&#32;&#61;&#32;&#98;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"55\" style=\"vertical-align: 0px;\"\/> produces the same sequence of (random) iterates <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-000395a193c65ba9e87c8c9b372099a4_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#104;&#97;&#116;&#123;&#120;&#125;&#95;&#116;\" title=\"Rendered by QuickLaTeX.com\" height=\"17\" width=\"15\" style=\"vertical-align: -3px;\"\/> as standard RK applied to the row-equilibrated system <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-b2a6be394fb5081fc8a94dafbc392d55_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#40;&#68;&#95;&#65;&#32;&#65;&#41;&#120;&#32;&#61;&#32;&#68;&#95;&#65;&#32;&#98;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"119\" style=\"vertical-align: -5px;\"\/>.<\/p>\n<\/blockquote>\n\n\n\n<p>Therefore, by (3), the iterates <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-000395a193c65ba9e87c8c9b372099a4_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#104;&#97;&#116;&#123;&#120;&#125;&#95;&#116;\" title=\"Rendered by QuickLaTeX.com\" height=\"17\" width=\"15\" style=\"vertical-align: -3px;\"\/> of uniform RK satisfy the bound <p class=\"ql-center-displayed-equation\" style=\"line-height: 32px;\"><span class=\"ql-right-eqno\"> (5) <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-3fc6402842af70a33954d0133066a5e3_l3.png\" height=\"32\" width=\"347\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#101;&#120;&#112;&#101;&#99;&#116;&#92;&#108;&#101;&#102;&#116;&#091;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#92;&#104;&#97;&#116;&#123;&#120;&#125;&#95;&#116;&#32;&#45;&#32;&#120;&#95;&#92;&#115;&#116;&#97;&#114;&#125;&#94;&#50;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#093;&#32;&#92;&#108;&#101;&#32;&#40;&#49;&#32;&#45;&#32;&#92;&#107;&#97;&#112;&#112;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#100;&#101;&#109;&#125;&#40;&#68;&#95;&#65;&#32;&#65;&#41;&#94;&#123;&#45;&#50;&#125;&#41;&#94;&#116;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#120;&#95;&#92;&#115;&#116;&#97;&#114;&#125;&#94;&#50;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>Thus, at least using the error bounds (3) and (5), whether standard or uniform RK is better depends on which matrix has a smaller Demmel condition number: <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-11f4f587954b361e7d78940f65b8d70d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"13\" style=\"vertical-align: 0px;\"\/> or <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-66c052278030d640588fb806f24d1a47_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#68;&#95;&#65;&#32;&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"39\" style=\"vertical-align: -3px;\"\/>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Row Equilibration and the Condition Number<\/h2>\n\n\n\n<p>Does row equilibration increase or decrease its condition number? What is the optimal way of scaling the rows of a matrix to minimize its condition number? These are classical questions in numerical linear algebra, and they were addressed in a <a href=\"https:\/\/doi.org\/10.1007\/BF02165096\">classical 1969 paper<\/a> of <a href=\"https:\/\/www.genealogy.math.ndsu.nodak.edu\/id.php?id=46005\">van der Sluis<\/a>. These results were then summarized and generalized in <a href=\"https:\/\/nhigham.com\">Higham&#8217;s<\/a> delightful monograph <em><a href=\"https:\/\/nhigham.com\/accuracy-and-stability-of-numerical-algorithms\/\">Accuracy and Stability of Numerical Algorithms<\/a><\/em>. Here, we present answers to these questions using a variant of van der Sluis&#8217; argument.<\/p>\n\n\n\n<p>First, let&#8217;s introduce some more concepts and notation. Define the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Matrix_norm#Spectral_norm_(p_=_2)\">spectral norm<\/a> <a href=\"https:\/\/en.wikipedia.org\/wiki\/Condition_number#Matrices\">condition number<\/a> <p class=\"ql-center-displayed-equation\" style=\"line-height: 43px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-3fb2bba4d99c34bc055f7043fccfe19c_l3.png\" height=\"43\" width=\"130\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#107;&#97;&#112;&#112;&#97;&#40;&#65;&#41;&#32;&#92;&#99;&#111;&#108;&#111;&#110;&#101;&#113;&#113;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#92;&#115;&#105;&#103;&#109;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#109;&#97;&#120;&#125;&#40;&#65;&#41;&#125;&#123;&#92;&#115;&#105;&#103;&#109;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#109;&#105;&#110;&#125;&#40;&#65;&#41;&#125;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>The spectral norm and Demmel condition numbers are always comparable <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-a2705fd69db0db01e845b34c6116bfe8_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#107;&#97;&#112;&#112;&#97;&#40;&#65;&#41;&#32;&#92;&#108;&#101;&#32;&#92;&#107;&#97;&#112;&#112;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#100;&#101;&#109;&#125;&#40;&#65;&#41;&#92;&#108;&#101;&#32;&#92;&#115;&#113;&#114;&#116;&#123;&#92;&#109;&#105;&#110;&#40;&#110;&#44;&#100;&#41;&#125;&#92;&#99;&#100;&#111;&#116;&#32;&#92;&#107;&#97;&#112;&#112;&#97;&#40;&#65;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"22\" width=\"286\" style=\"vertical-align: -6px;\"\/>. Also, let <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-8ee3a539f3fae2627adb7ad8cd47a605_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#109;&#97;&#116;&#104;&#114;&#109;&#123;&#68;&#105;&#97;&#103;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"37\" style=\"vertical-align: -4px;\"\/> denote the set of all (nonsingular) diagonal matrices.<\/p>\n\n\n\n<p>Our first result shows us that row equilibration never hurts the Demmel condition number by much. In fact, the row-equilibrated matrix produces a nearly optimal Demmel condition number when compared to any row scaling:<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p><strong>Theorem 1 (Row equilibration is a nearly optimal row scaling).<\/strong> Let <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-0841be6dc58385d95def9f4ab1b55a3c_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;&#92;&#105;&#110;&#92;&#114;&#101;&#97;&#108;&#94;&#123;&#110;&#92;&#116;&#105;&#109;&#101;&#115;&#32;&#100;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"75\" style=\"vertical-align: -1px;\"\/> be wide <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-6b90b6c5867bf4c43ef5a9a2e22313fa_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#110;&#92;&#108;&#101;&#32;&#100;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"44\" style=\"vertical-align: -3px;\"\/> and full-rank, and let <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-c33b29335100f350ef1dd17a013c50ec_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#68;&#95;&#65;&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"39\" style=\"vertical-align: -3px;\"\/> denote the row-scaling of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-11f4f587954b361e7d78940f65b8d70d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"13\" style=\"vertical-align: 0px;\"\/> to have unit row norms. Then <p class=\"ql-center-displayed-equation\" style=\"line-height: 30px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-ec117b2c8c81cbcfc88eeae87eac0aaa_l3.png\" height=\"30\" width=\"452\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#107;&#97;&#112;&#112;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#100;&#101;&#109;&#125;&#40;&#68;&#95;&#65;&#65;&#41;&#32;&#92;&#108;&#101;&#32;&#92;&#115;&#113;&#114;&#116;&#123;&#110;&#125;&#92;&#99;&#100;&#111;&#116;&#32;&#92;&#109;&#105;&#110;&#95;&#123;&#68;&#32;&#92;&#105;&#110;&#32;&#92;&#109;&#97;&#116;&#104;&#114;&#109;&#123;&#68;&#105;&#97;&#103;&#125;&#125;&#32;&#92;&#107;&#97;&#112;&#112;&#97;&#32;&#40;&#68;&#65;&#41;&#32;&#92;&#108;&#101;&#32;&#92;&#115;&#113;&#114;&#116;&#123;&#110;&#125;&#92;&#99;&#100;&#111;&#116;&#32;&#92;&#109;&#105;&#110;&#95;&#123;&#68;&#32;&#92;&#105;&#110;&#32;&#92;&#109;&#97;&#116;&#104;&#114;&#109;&#123;&#68;&#105;&#97;&#103;&#125;&#125;&#32;&#92;&#107;&#97;&#112;&#112;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#100;&#101;&#109;&#125;&#32;&#40;&#68;&#65;&#41;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n<\/blockquote>\n\n\n\n<p>By scaling the rows of a square or wide matrix to have unit norm, we bring the Demmel condition number to within a <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-0bbb71c94391d90ce47d108084081941_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#115;&#113;&#114;&#116;&#123;&#110;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"18\" width=\"25\" style=\"vertical-align: -4px;\"\/> factor of the optimal row scaling. In fact, we even bring the Demmel condition number to within a <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-0bbb71c94391d90ce47d108084081941_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#115;&#113;&#114;&#116;&#123;&#110;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"18\" width=\"25\" style=\"vertical-align: -4px;\"\/> factor of the optimal <em>spectral norm condition number<\/em> for any row scaling.<\/p>\n\n\n\n<p>Since the convergence rate for randomized Kaczmarz is <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-e1b1d795b76e5832593447c998401556_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#107;&#97;&#112;&#112;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#100;&#101;&#109;&#125;&#40;&#65;&#41;&#94;&#123;&#45;&#50;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"20\" width=\"81\" style=\"vertical-align: -5px;\"\/>, this result shows that implementing randomized Kaczmarz with uniform sampling yields to a convergence rate that is within a factor of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-75a5652acadcd645b180a972b75a9d09_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#110;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"11\" style=\"vertical-align: 0px;\"\/> of the optimal convergence rate using any possible sampling distribution.<\/p>\n\n\n\n<p>This result shows us that row equilibration can&#8217;t <em>hurt<\/em> the Demmel condition number by much. But can it help? The following proposition shows that it can help <em>a lot<\/em> for some problems.<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p><strong>Proposition 2 (Row equilibration can help a lot).<\/strong> Let <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-0841be6dc58385d95def9f4ab1b55a3c_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;&#92;&#105;&#110;&#92;&#114;&#101;&#97;&#108;&#94;&#123;&#110;&#92;&#116;&#105;&#109;&#101;&#115;&#32;&#100;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"75\" style=\"vertical-align: -1px;\"\/> be wide <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-6b90b6c5867bf4c43ef5a9a2e22313fa_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#110;&#92;&#108;&#101;&#32;&#100;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"44\" style=\"vertical-align: -3px;\"\/> and full-rank, and let <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-939f5daebaa434944b83ad6cb67e1a65_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#103;&#97;&#109;&#109;&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"10\" style=\"vertical-align: -4px;\"\/> denote the maximum ratio between two row norms: <p class=\"ql-center-displayed-equation\" style=\"line-height: 43px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-9289f9e9a0f729efb516fbda78ac3453_l3.png\" height=\"43\" width=\"119\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#103;&#97;&#109;&#109;&#97;&#32;&#92;&#99;&#111;&#108;&#111;&#110;&#101;&#113;&#113;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#32;&#92;&#109;&#97;&#120;&#95;&#105;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#97;&#95;&#105;&#125;&#125;&#123;&#92;&#109;&#105;&#110;&#95;&#105;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#97;&#95;&#105;&#125;&#125;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>Then the Demmel condition number of the original matrix <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-11f4f587954b361e7d78940f65b8d70d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"13\" style=\"vertical-align: 0px;\"\/> satisfies <p class=\"ql-center-displayed-equation\" style=\"line-height: 19px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-d842439abf3ace1c3c590d983ec36107_l3.png\" height=\"19\" width=\"203\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#107;&#97;&#112;&#112;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#100;&#101;&#109;&#125;&#40;&#65;&#41;&#32;&#92;&#108;&#101;&#32;&#92;&#103;&#97;&#109;&#109;&#97;&#32;&#92;&#99;&#100;&#111;&#116;&#32;&#92;&#107;&#97;&#112;&#112;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#100;&#101;&#109;&#125;&#40;&#68;&#95;&#65;&#32;&#65;&#41;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>Moreover, for every <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-0067d06a2f823af247f7759175ee2e94_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#103;&#97;&#109;&#109;&#97;&#92;&#103;&#101;&#32;&#49;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"42\" style=\"vertical-align: -4px;\"\/>, there exists a matrix <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-cf95ea79e5ae8a03bac24fde423ad2f3_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;&#95;&#92;&#103;&#97;&#109;&#109;&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"21\" style=\"vertical-align: -6px;\"\/> where this bound is nearly attained: <p class=\"ql-center-displayed-equation\" style=\"line-height: 43px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-9ff68e369e8f22f56563fdc443894ce4_l3.png\" height=\"43\" width=\"304\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#107;&#97;&#112;&#112;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#100;&#101;&#109;&#125;&#40;&#65;&#95;&#92;&#103;&#97;&#109;&#109;&#97;&#41;&#32;&#92;&#103;&#101;&#32;&#92;&#115;&#113;&#114;&#116;&#123;&#49;&#45;&#92;&#102;&#114;&#97;&#99;&#123;&#49;&#125;&#123;&#110;&#125;&#125;&#32;&#92;&#99;&#100;&#111;&#116;&#32;&#92;&#103;&#97;&#109;&#109;&#97;&#32;&#92;&#99;&#100;&#111;&#116;&#32;&#92;&#107;&#97;&#112;&#112;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#100;&#101;&#109;&#125;&#40;&#68;&#95;&#123;&#65;&#95;&#92;&#103;&#97;&#109;&#109;&#97;&#125;&#65;&#95;&#92;&#103;&#97;&#109;&#109;&#97;&#41;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n<\/blockquote>\n\n\n\n<p>Taken together, Theorem 1 and Proposition 2 show that row equilibration often improves the Demmel condition number, and never increases it by that much. Consequently, uniform RK often converges faster than standard RK for square (or short wide) linear systems, and it never converges much slower.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Proof of Theorem 1<\/h3>\n\n\n\n<p>We follow Higham&#8217;s approach. Each of the <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-75a5652acadcd645b180a972b75a9d09_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#110;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"11\" style=\"vertical-align: 0px;\"\/> rows of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-c33b29335100f350ef1dd17a013c50ec_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#68;&#95;&#65;&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"39\" style=\"vertical-align: -3px;\"\/> each have unit norm, so <p class=\"ql-center-displayed-equation\" style=\"line-height: 20px;\"><span class=\"ql-right-eqno\"> (7) <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-dc083ac4d61189b0851e1495ff99f25d_l3.png\" height=\"20\" width=\"117\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#110;&#111;&#114;&#109;&#123;&#68;&#95;&#65;&#65;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#32;&#61;&#32;&#92;&#115;&#113;&#114;&#116;&#123;&#110;&#125;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>The minimum singular value of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-66c052278030d640588fb806f24d1a47_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#68;&#95;&#65;&#32;&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"39\" style=\"vertical-align: -3px;\"\/> can be written in terms of the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Moore\u2013Penrose_inverse\">Moore\u2013Penrose pseudoinverse<\/a> <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-d675181ee3dd75c00f1a127964f85890_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#40;&#68;&#95;&#65;&#32;&#65;&#41;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#61;&#32;&#65;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#68;&#95;&#65;&#94;&#123;&#45;&#49;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"22\" width=\"135\" style=\"vertical-align: -6px;\"\/> as follows <p class=\"ql-center-displayed-equation\" style=\"line-height: 41px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-c96cc4653bb180133ed40dd1c84687fd_l3.png\" height=\"41\" width=\"193\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#102;&#114;&#97;&#99;&#123;&#49;&#125;&#123;&#92;&#115;&#105;&#103;&#109;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#109;&#105;&#110;&#125;&#40;&#68;&#95;&#65;&#32;&#65;&#41;&#125;&#32;&#61;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#65;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#68;&#95;&#65;&#94;&#123;&#45;&#49;&#125;&#125;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>Here, <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-6db2c55dc3ba238574def17c6c8dac26_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#110;&#111;&#114;&#109;&#123;&#92;&#99;&#100;&#111;&#116;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"19\" style=\"vertical-align: -5px;\"\/> denotes the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Matrix_norm#Spectral_norm_(p_=_2)\">spectral norm<\/a>. Then for any nonsingular diagonal matrix <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-ab69a4a7716bbf890e5f604a06fd1f13_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#68;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"15\" style=\"vertical-align: 0px;\"\/>, we have <p class=\"ql-center-displayed-equation\" style=\"line-height: 47px;\"><span class=\"ql-right-eqno\"> (8) <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-a65986b5ef3ac5975280bffcd2fcb927_l3.png\" height=\"47\" width=\"525\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#102;&#114;&#97;&#99;&#123;&#49;&#125;&#123;&#92;&#115;&#105;&#103;&#109;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#109;&#105;&#110;&#125;&#40;&#68;&#95;&#65;&#32;&#65;&#41;&#125;&#32;&#61;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#65;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#68;&#94;&#123;&#45;&#49;&#125;&#32;&#40;&#68;&#68;&#95;&#65;&#94;&#123;&#45;&#49;&#125;&#41;&#125;&#32;&#92;&#108;&#101;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#65;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#68;&#94;&#123;&#45;&#49;&#125;&#125;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#68;&#68;&#95;&#65;&#94;&#123;&#45;&#49;&#125;&#125;&#32;&#61;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#92;&#110;&#111;&#114;&#109;&#123;&#68;&#68;&#95;&#65;&#94;&#123;&#45;&#49;&#125;&#125;&#125;&#123;&#92;&#115;&#105;&#103;&#109;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#109;&#105;&#110;&#125;&#40;&#68;&#65;&#41;&#125;&#46;&#32;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>Since the matrix <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-eda5b6f59739a3b834ca020d7ee97f84_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#68;&#68;&#95;&#65;&#94;&#123;&#45;&#49;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"22\" width=\"47\" style=\"vertical-align: -6px;\"\/> is diagonal its spectral norm is <p class=\"ql-center-displayed-equation\" style=\"line-height: 43px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-705ca33a5372c0bdf858770f9d204436_l3.png\" height=\"43\" width=\"311\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#110;&#111;&#114;&#109;&#123;&#68;&#68;&#95;&#65;&#94;&#123;&#45;&#49;&#125;&#125;&#32;&#61;&#32;&#92;&#109;&#97;&#120;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#123;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#124;&#68;&#95;&#123;&#105;&#105;&#125;&#124;&#125;&#123;&#124;&#40;&#68;&#95;&#65;&#41;&#95;&#123;&#105;&#105;&#125;&#124;&#125;&#32;&#58;&#32;&#49;&#92;&#108;&#101;&#32;&#105;&#32;&#92;&#108;&#101;&#32;&#110;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#125;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>The diagonal entries of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-144dd4f09610618a6afa46a2437469d1_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#68;&#95;&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"25\" style=\"vertical-align: -3px;\"\/> are <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-a5112751ea9667732a811368417cf9d1_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#110;&#111;&#114;&#109;&#123;&#97;&#95;&#105;&#125;&#94;&#123;&#45;&#49;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"22\" width=\"48\" style=\"vertical-align: -5px;\"\/>, so <p class=\"ql-center-displayed-equation\" style=\"line-height: 23px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-b8026880c5418d6aac0894b839079753_l3.png\" height=\"23\" width=\"301\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#110;&#111;&#114;&#109;&#123;&#68;&#68;&#95;&#65;&#94;&#123;&#45;&#49;&#125;&#125;&#32;&#61;&#32;&#92;&#109;&#97;&#120;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#123;&#32;&#124;&#68;&#95;&#123;&#105;&#105;&#125;&#124;&#92;&#110;&#111;&#114;&#109;&#123;&#97;&#95;&#105;&#125;&#32;&#58;&#32;&#49;&#92;&#108;&#101;&#32;&#105;&#92;&#108;&#101;&#32;&#110;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#125;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>is the maximum row norm of the scaled matrix <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-8d56b0da58e06a626a9b273cc6291ecf_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#68;&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"28\" style=\"vertical-align: 0px;\"\/>. The maximum row norm is always less than the largest singular value of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-8d56b0da58e06a626a9b273cc6291ecf_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#68;&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"28\" style=\"vertical-align: 0px;\"\/>, so <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-5db9c4cf8726e54fc1f67db25d4c7909_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#110;&#111;&#114;&#109;&#123;&#68;&#68;&#95;&#65;&#94;&#123;&#45;&#49;&#125;&#125;&#32;&#92;&#108;&#101;&#32;&#92;&#115;&#105;&#103;&#109;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#109;&#97;&#120;&#125;&#40;&#68;&#65;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"23\" width=\"168\" style=\"vertical-align: -7px;\"\/>. Therefore, combining this result, (7), and (9), we obtain <p class=\"ql-center-displayed-equation\" style=\"line-height: 43px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-9e73680b6f4fe21817d43adb57a457ff_l3.png\" height=\"43\" width=\"352\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#107;&#97;&#112;&#112;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#100;&#101;&#109;&#125;&#40;&#68;&#95;&#65;&#65;&#41;&#32;&#92;&#108;&#101;&#32;&#92;&#115;&#113;&#114;&#116;&#123;&#110;&#125;&#32;&#92;&#99;&#100;&#111;&#116;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#92;&#115;&#105;&#103;&#109;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#109;&#97;&#120;&#125;&#40;&#68;&#65;&#41;&#125;&#123;&#92;&#115;&#105;&#103;&#109;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#109;&#105;&#110;&#125;&#40;&#68;&#65;&#41;&#125;&#32;&#61;&#32;&#92;&#115;&#113;&#114;&#116;&#123;&#110;&#125;&#92;&#99;&#100;&#111;&#116;&#32;&#92;&#107;&#97;&#112;&#112;&#97;&#32;&#40;&#68;&#65;&#41;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>Since this bound holds for every <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-97ce0d4a42a281949b8f87dd8b4a0dcc_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#68;&#32;&#92;&#105;&#110;&#32;&#92;&#109;&#97;&#116;&#104;&#114;&#109;&#123;&#68;&#105;&#97;&#103;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"74\" style=\"vertical-align: -4px;\"\/>, we are free to minimize over <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-ab69a4a7716bbf890e5f604a06fd1f13_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#68;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"15\" style=\"vertical-align: 0px;\"\/>, leading to the first inequality in the theorem: <p class=\"ql-center-displayed-equation\" style=\"line-height: 30px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-e18d74284219efc70ced6833db98a733_l3.png\" height=\"30\" width=\"259\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#107;&#97;&#112;&#112;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#100;&#101;&#109;&#125;&#40;&#68;&#95;&#65;&#65;&#41;&#32;&#92;&#108;&#101;&#32;&#92;&#115;&#113;&#114;&#116;&#123;&#110;&#125;&#92;&#99;&#100;&#111;&#116;&#32;&#92;&#109;&#105;&#110;&#95;&#123;&#68;&#32;&#92;&#105;&#110;&#32;&#92;&#109;&#97;&#116;&#104;&#114;&#109;&#123;&#68;&#105;&#97;&#103;&#125;&#125;&#32;&#92;&#107;&#97;&#112;&#112;&#97;&#32;&#40;&#68;&#65;&#41;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>Since the spectral norm condition number is smaller than the Demmel condition number, we obtain the second bound in the theorem.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Proof of Proposition 2<\/h3>\n\n\n\n<p>Write <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-f4175d1e690e5147dba355f299283b35_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;&#32;&#61;&#32;&#68;&#95;&#65;&#94;&#123;&#45;&#49;&#125;&#40;&#68;&#95;&#65;&#65;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"22\" width=\"122\" style=\"vertical-align: -6px;\"\/>. Using the Moore\u2013Penrose pseudoinverse again, write <p class=\"ql-center-displayed-equation\" style=\"line-height: 34px;\"><span class=\"ql-right-eqno\"> (10) <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-50cf827241cc20f905230e4a51946d0b_l3.png\" height=\"34\" width=\"318\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#107;&#97;&#112;&#112;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#100;&#101;&#109;&#125;&#40;&#65;&#41;&#32;&#61;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#68;&#95;&#65;&#94;&#123;&#45;&#49;&#125;&#40;&#68;&#95;&#65;&#65;&#41;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#40;&#68;&#95;&#65;&#32;&#65;&#41;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#68;&#95;&#65;&#125;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>The Frobenius norm and spectral norm satisfy a (mixed) submultiplicative property <p class=\"ql-center-displayed-equation\" style=\"line-height: 19px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-051f8f43c351dcc02a4d3342d55b5455_l3.png\" height=\"19\" width=\"325\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#110;&#111;&#114;&#109;&#123;&#66;&#67;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#32;&#92;&#108;&#101;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#66;&#125;&#92;&#110;&#111;&#114;&#109;&#123;&#67;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#44;&#32;&#92;&#113;&#117;&#97;&#100;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#66;&#67;&#125;&#32;&#92;&#108;&#101;&#92;&#110;&#111;&#114;&#109;&#123;&#66;&#125;&#92;&#110;&#111;&#114;&#109;&#123;&#67;&#125;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>Applying this result to (1), we obtain <p class=\"ql-center-displayed-equation\" style=\"line-height: 34px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-1d3aa06275558feecad7fe4a38c3f64a_l3.png\" height=\"34\" width=\"345\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#107;&#97;&#112;&#112;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#100;&#101;&#109;&#125;&#40;&#65;&#41;&#32;&#92;&#108;&#101;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#68;&#95;&#65;&#94;&#123;&#45;&#49;&#125;&#125;&#92;&#110;&#111;&#114;&#109;&#123;&#68;&#95;&#65;&#65;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#40;&#68;&#95;&#65;&#32;&#65;&#41;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#125;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#68;&#95;&#65;&#125;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>We recognize <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-8fc10486023f88fc11fca91cedbc1ad7_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#103;&#97;&#109;&#109;&#97;&#32;&#61;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#68;&#95;&#65;&#94;&#123;&#45;&#49;&#125;&#125;&#92;&#110;&#111;&#114;&#109;&#123;&#68;&#95;&#65;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"23\" width=\"132\" style=\"vertical-align: -7px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-8f1966fb6129c5154bdbc8c398955fc6_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#107;&#97;&#112;&#112;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#100;&#101;&#109;&#125;&#40;&#68;&#95;&#65;&#32;&#65;&#41;&#32;&#61;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#68;&#95;&#65;&#65;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#40;&#68;&#95;&#65;&#32;&#65;&#41;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"23\" width=\"260\" style=\"vertical-align: -7px;\"\/>. We conclude <p class=\"ql-center-displayed-equation\" style=\"line-height: 19px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-d842439abf3ace1c3c590d983ec36107_l3.png\" height=\"19\" width=\"203\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#107;&#97;&#112;&#112;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#100;&#101;&#109;&#125;&#40;&#65;&#41;&#32;&#92;&#108;&#101;&#32;&#92;&#103;&#97;&#109;&#109;&#97;&#32;&#92;&#99;&#100;&#111;&#116;&#32;&#92;&#107;&#97;&#112;&#112;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#100;&#101;&#109;&#125;&#40;&#68;&#95;&#65;&#32;&#65;&#41;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>To show this bound is nearly obtained, introduce <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-c7d2168324d33967a68c3b245c3fc900_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;&#95;&#92;&#103;&#97;&#109;&#109;&#97;&#32;&#61;&#32;&#92;&#100;&#105;&#97;&#103;&#40;&#92;&#103;&#97;&#109;&#109;&#97;&#44;&#92;&#103;&#97;&#109;&#109;&#97;&#44;&#92;&#108;&#100;&#111;&#116;&#115;&#44;&#92;&#103;&#97;&#109;&#109;&#97;&#44;&#49;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"20\" width=\"153\" style=\"vertical-align: -6px;\"\/>. Then <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-344da55bd253fee38c10d0a46c5c46ea_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#68;&#95;&#123;&#65;&#95;&#92;&#103;&#97;&#109;&#109;&#97;&#125;&#32;&#65;&#95;&#92;&#103;&#97;&#109;&#109;&#97;&#32;&#61;&#32;&#73;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"88\" style=\"vertical-align: -6px;\"\/> with <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-fa06f42f79ef0f16d78b93dd6fb47156_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#107;&#97;&#112;&#112;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#100;&#101;&#109;&#125;&#40;&#68;&#95;&#123;&#65;&#95;&#92;&#103;&#97;&#109;&#109;&#97;&#125;&#65;&#95;&#123;&#92;&#103;&#97;&#109;&#109;&#97;&#125;&#41;&#32;&#61;&#32;&#92;&#115;&#113;&#114;&#116;&#123;&#110;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"20\" width=\"155\" style=\"vertical-align: -6px;\"\/> and <p class=\"ql-center-displayed-equation\" style=\"line-height: 46px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-0216b29d23ab394e7040423bd9a13ebe_l3.png\" height=\"46\" width=\"469\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#107;&#97;&#112;&#112;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#100;&#101;&#109;&#125;&#40;&#65;&#95;&#92;&#103;&#97;&#109;&#109;&#97;&#41;&#32;&#61;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#92;&#110;&#111;&#114;&#109;&#123;&#65;&#95;&#123;&#92;&#103;&#97;&#109;&#109;&#97;&#125;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#125;&#123;&#92;&#115;&#105;&#103;&#109;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#109;&#105;&#110;&#125;&#40;&#65;&#95;&#92;&#103;&#97;&#109;&#109;&#97;&#41;&#125;&#32;&#61;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#92;&#115;&#113;&#114;&#116;&#123;&#40;&#110;&#45;&#49;&#41;&#92;&#103;&#97;&#109;&#109;&#97;&#94;&#50;&#43;&#49;&#125;&#125;&#123;&#49;&#125;&#32;&#92;&#103;&#101;&#32;&#92;&#115;&#113;&#114;&#116;&#123;&#110;&#125;&#32;&#92;&#99;&#100;&#111;&#116;&#32;&#92;&#115;&#113;&#114;&#116;&#123;&#49;&#45;&#92;&#102;&#114;&#97;&#99;&#123;&#49;&#125;&#123;&#110;&#125;&#125;&#32;&#92;&#99;&#100;&#111;&#116;&#32;&#92;&#103;&#97;&#109;&#109;&#97;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>Therefore, <p class=\"ql-center-displayed-equation\" style=\"line-height: 43px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-9ff68e369e8f22f56563fdc443894ce4_l3.png\" height=\"43\" width=\"304\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#107;&#97;&#112;&#112;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#100;&#101;&#109;&#125;&#40;&#65;&#95;&#92;&#103;&#97;&#109;&#109;&#97;&#41;&#32;&#92;&#103;&#101;&#32;&#92;&#115;&#113;&#114;&#116;&#123;&#49;&#45;&#92;&#102;&#114;&#97;&#99;&#123;&#49;&#125;&#123;&#110;&#125;&#125;&#32;&#92;&#99;&#100;&#111;&#116;&#32;&#92;&#103;&#97;&#109;&#109;&#97;&#32;&#92;&#99;&#100;&#111;&#116;&#32;&#92;&#107;&#97;&#112;&#112;&#97;&#95;&#123;&#92;&#114;&#109;&#32;&#100;&#101;&#109;&#125;&#40;&#68;&#95;&#123;&#65;&#95;&#92;&#103;&#97;&#109;&#109;&#97;&#125;&#65;&#95;&#92;&#103;&#97;&#109;&#109;&#97;&#41;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Practical Guidance<\/h2>\n\n\n\n<p>What does this theory mean for practice? Ultimately, single-row randomized Kaczmarz is often not the best algorithm for the job for ordinary square (or short\u2013wide) linear systems, anyway\u2014<a href=\"https:\/\/arxiv.org\/abs\/1208.3805\">block Kaczmarz<\/a> or (<a href=\"https:\/\/en.wikipedia.org\/wiki\/Iterative_method#Preconditioners\">preconditioned<\/a>) <a href=\"https:\/\/en.wikipedia.org\/wiki\/Iterative_method#Krylov_subspace_methods\">Krylov methods<\/a> have been faster in my experience. But, supposing that we have locked in (single-row) randomized Kaczmarz as our algorithm, how should we implement it?<\/p>\n\n\n\n<p>This question is hard to answer, because there are examples where standard RK and uniform RK both converge faster than the other. Theorem 1 suggests uniform RK can require as many as <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-fb7d69d134ae116cbbfcda909673a258_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#110;&#92;&#116;&#105;&#109;&#101;&#115;\" title=\"Rendered by QuickLaTeX.com\" height=\"9\" width=\"23\" style=\"vertical-align: 0px;\"\/> more iterations than standard RK on a worst-case example, which can be a big difference for large problems. But, particularly for badly row-scaled problems, Proposition 2 shows that uniform RK can dramatically outcompete standard RK. Ultimately, I would give two answers.<\/p>\n\n\n\n<p>First, if the matrix <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-11f4f587954b361e7d78940f65b8d70d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"13\" style=\"vertical-align: 0px;\"\/> has already been carefully designed to be well-conditioned and computing the row norms is not computationally burdensome, then standard RK may be worth the effort. Despite this theory suggesting it can do quite badly, it took a bit of effort to construct a simple example of a &#8220;bad&#8221; matrix where uniform RK significantly outcompeted standard RK. (On most examples I constructed, the rate of convergence of the two methods were similar.)<\/p>\n\n\n\n<p>Second, particularly for the largest systems where you only want to make a small number of total passes over the matrix, expending a full pass over the matrix to compute the row norms is a significant expense. And, for poorly row-scaled matrices, sampling using the squared row norms can hurt the convergence rate. Based on these observations, given a matrix of unknown row scaling and conditioning or given a small budget of passes over the matrix, I would use the uniform RK method over the standard RK method.<\/p>\n\n\n\n<p>Finally, let me again emphasize that the theoretical results Theorem 1 and Proposition 2 <mark style=\"background-color:#fff4d7\" class=\"has-inline-color\"><em>only apply to square or wide matrices<\/em> <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-11f4f587954b361e7d78940f65b8d70d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"13\" style=\"vertical-align: 0px;\"\/>.<\/mark> Uniform RK also appears to work for <em><a href=\"https:\/\/en.wikipedia.org\/wiki\/System_of_linear_equations#Consistency\">consistent<\/a><\/em> systems with a tall matrix, but I am unaware of a theoretical result comparing the Demmel condition numbers of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-c33b29335100f350ef1dd17a013c50ec_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#68;&#95;&#65;&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"39\" style=\"vertical-align: -3px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-11f4f587954b361e7d78940f65b8d70d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"13\" style=\"vertical-align: 0px;\"\/> that applies to tall matrices. And for inconsistent systems of equations, it&#8217;s a <a href=\"https:\/\/www.ethanepperly.com\/index.php\/2024\/12\/02\/randomized-kaczmarz-is-asympotically-unbiased-for-least-squares\/#what-least-squares-solution-are-we-converging-to\">whole different story<\/a>.<\/p>\n\n\n\n<p><strong><em>Edit<\/em><\/strong>: After initial publication of this post, Mark Schmidt shared that the observation that uniform RK can outperform standard RK was made nearly ten years ago in section 4.2 of <a href=\"https:\/\/arxiv.org\/abs\/1612.07838\">the following paper<\/a>. They support this observation with a different mathematical justification <\/p>\n","protected":false},"excerpt":{"rendered":"<p>The randomized Kaczmarz method is a method for solving systems of linear equations: (1) &nbsp; Throughout this post, the matrix will have dimensions . Beginning from an initial iterate , randomized Kaczmarz works as follows. For : What selection probabilities should we use? The answer to this question may depend on whether the system (1)<a class=\"more-link\" href=\"https:\/\/www.ethanepperly.com\/index.php\/2025\/06\/16\/randomized-kaczmarz-how-should-you-sample\/\">Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6,16],"tags":[],"class_list":["post-2019","post","type-post","status-publish","format-standard","hentry","category-expository","category-randomized-kaczmarz"],"_links":{"self":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts\/2019","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/comments?post=2019"}],"version-history":[{"count":14,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts\/2019\/revisions"}],"predecessor-version":[{"id":2126,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts\/2019\/revisions\/2126"}],"wp:attachment":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/media?parent=2019"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/categories?post=2019"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/tags?post=2019"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}