{"id":1529,"date":"2023-06-22T00:51:51","date_gmt":"2023-06-22T00:51:51","guid":{"rendered":"https:\/\/www.ethanepperly.com\/?p=1529"},"modified":"2025-04-29T02:04:03","modified_gmt":"2025-04-29T02:04:03","slug":"low-rank-approximation-toolbox-analysis-of-the-randomized-svd","status":"publish","type":"post","link":"https:\/\/www.ethanepperly.com\/index.php\/2023\/06\/22\/low-rank-approximation-toolbox-analysis-of-the-randomized-svd\/","title":{"rendered":"Low-Rank Approximation Toolbox: Analysis of the Randomized SVD"},"content":{"rendered":"\n<p>In the <a href=\"https:\/\/www.ethanepperly.com\/index.php\/2023\/06\/12\/low-rank-approximation-toolbox-randomized-svd\/\">previous post<\/a>, we looked at the randomized SVD. In this post, we continue this discussion by looking at the <em>analysis<\/em> of the randomized SVD. Our approach is adapted from a <a href=\"https:\/\/arxiv.org\/abs\/2306.12418\">new analysis of the randomized SVD<\/a> by <a href=\"https:\/\/tropp.caltech.edu\">Joel A. Tropp<\/a> and <a href=\"https:\/\/rwebber.people.caltech.edu\">Robert J. Webber<\/a>.<\/p>\n\n\n\n<p>There are many types of analysis one can do for the randomized SVD. For instance, letting <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-06d2c1a5a171b6d7d9c5df87d123c5a4_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#66;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/> be a matrix and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-ee8974e4adfbdab75fa43f4df80b4e5d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#88;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"16\" style=\"vertical-align: 0px;\"\/> the rank-<img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-f65286b751f121928913d4aa91d94ee9_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: 0px;\"\/> output of the randomized SVD, natural questions include:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>What is the <a href=\"https:\/\/en.m.wikipedia.org\/wiki\/Expected_value\">expected<\/a> error <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-69c8acf10ef5670b854e953e4a1645ce_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#69;&#125;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#88;&#45;&#66;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"83\" style=\"vertical-align: -5px;\"\/> measured in some <a href=\"https:\/\/en.m.wikipedia.org\/wiki\/Norm_(mathematics)\">norm<\/a> <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;\"\/>? What about expected squared error <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-cf6a6bef7fb9df1c485be30a44d1dcab_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#69;&#125;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#88;&#45;&#66;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#94;&#50;\" title=\"Rendered by QuickLaTeX.com\" height=\"22\" width=\"92\" style=\"vertical-align: -5px;\"\/>? How do these answers change with different norms?<\/li>\n\n\n\n<li>How large can the randomized SVD error <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-71748e1abd52ce116b03b2e2fe2fc241_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#110;&#111;&#114;&#109;&#123;&#88;&#32;&#45;&#32;&#66;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"66\" style=\"vertical-align: -5px;\"\/> get except for some small failure probability <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-50f767701973c5f8f4cb8cc6ed459bad_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#100;&#101;&#108;&#116;&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"8\" style=\"vertical-align: 0px;\"\/>?<\/li>\n\n\n\n<li>How close is the randomized SVD <em>truncated to rank <\/em><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-7b919ac10b1842ce6c184b39f6af86a6_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#114;&#104;&#111;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: -4px;\"\/> compared to the best rank-<em><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-7b919ac10b1842ce6c184b39f6af86a6_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#114;&#104;&#111;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: -4px;\"\/> approximation to <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-06d2c1a5a171b6d7d9c5df87d123c5a4_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#66;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/>?<\/em><\/li>\n\n\n\n<li>How close are the <a href=\"https:\/\/en.m.wikipedia.org\/wiki\/Singular_value\">singular values<\/a> and <a href=\"https:\/\/en.m.wikipedia.org\/wiki\/Singular_value_decomposition\">vectors<\/a> of the randomized SVD approximation <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-ee8974e4adfbdab75fa43f4df80b4e5d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#88;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"16\" style=\"vertical-align: 0px;\"\/> compared to those of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-06d2c1a5a171b6d7d9c5df87d123c5a4_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#66;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/>?<\/li>\n<\/ul>\n\n\n\n<p>Implicitly and explicitly, <a href=\"https:\/\/arxiv.org\/abs\/2306.12418\">the analysis of Tropp and Webber<\/a> provides satisfactory answers to a number of these questions. In the interest of simplifying the presentation, we shall focus our presentation on just one of these questions, proving following result:<\/p>\n\n\n\n<p><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-6759ab11982f765f19dc615fb8e1fbdc_l3.png\" height=\"43\" width=\"537\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#69;&#125;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#66;&#45;&#88;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#32;&#92;&#108;&#101;&#32;&#92;&#108;&#101;&#102;&#116;&#40;&#32;&#49;&#32;&#43;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#107;&#125;&#123;&#107;&#45;&#40;&#114;&#43;&#49;&#41;&#125;&#92;&#114;&#105;&#103;&#104;&#116;&#41;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#66;&#32;&#45;&#32;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#32;&#92;&#113;&#117;&#97;&#100;&#32;&#92;&#116;&#101;&#120;&#116;&#123;&#102;&#111;&#114;&#32;&#101;&#118;&#101;&#114;&#121;&#32;&#36;&#114;&#32;&#92;&#108;&#101;&#32;&#107;&#45;&#50;&#36;&#125;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>Here, <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-21aa741b21cd9ddd67cb1b55b6d531ac_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#99;&#100;&#111;&#116;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"30\" style=\"vertical-align: -5px;\"\/> is the <em><a href=\"https:\/\/en.m.wikipedia.org\/wiki\/Matrix_norm#Frobenius_norm\">Frobenius norm<\/a><\/em>. We encourage the interested reader to check out <a href=\"https:\/\/arxiv.org\/abs\/2306.12418\">Tropp and Webber&#8217;s paper<\/a> to see the methodology we summarize here used to prove numerous facts about the randomized SVD and its extensions using subspace iteration and block Krylov iteration.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Projection Formula<\/h2>\n\n\n\n<p>Let us recall the randomized SVD as we presented it in last post:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Collect information.<\/strong> Form <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-99f2b6ea36209285753eadbdefaf7dbb_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#89;&#32;&#61;&#32;&#66;&#92;&#79;&#109;&#101;&#103;&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"64\" style=\"vertical-align: 0px;\"\/> where <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-0e42a68047144196ffa9763b964056ac_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#79;&#109;&#101;&#103;&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"12\" style=\"vertical-align: 0px;\"\/> is an appropriately chosen <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-1a55278ecc061a49dac84a0a29899010_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#110;&#92;&#116;&#105;&#109;&#101;&#115;&#32;&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"41\" style=\"vertical-align: 0px;\"\/> random matrix.<\/li>\n\n\n\n<li><strong>Orthogonalize.<\/strong> Compute an orthonormal basis <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-e7f252699e1616398a7ce5179d3e425e_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#81;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"14\" style=\"vertical-align: -4px;\"\/> for the column space of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-58d456b42236adc71c7788a42a6c7884_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#89;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/> by, e.g., <a href=\"https:\/\/en.m.wikipedia.org\/wiki\/QR_decomposition#Rectangular_matrix\">thin QR factorization<\/a>.<\/li>\n\n\n\n<li><strong>Project.<\/strong> Form <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-bd73898692f99da98e6827f593af189f_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#67;&#32;&#92;&#99;&#111;&#108;&#111;&#110;&#101;&#113;&#113;&#32;&#81;&#94;&#42;&#66;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"77\" style=\"vertical-align: -4px;\"\/>, where <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-c15a9e678f5eb8ef071c71b328820967_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#123;&#125;&#94;&#42;\" title=\"Rendered by QuickLaTeX.com\" height=\"6\" width=\"6\" style=\"vertical-align: 6px;\"\/> denotes the <a href=\"https:\/\/en.m.wikipedia.org\/wiki\/Conjugate_transpose\">conjugate transpose<\/a>.<\/li>\n<\/ol>\n\n\n\n<p>The randomized SVD is the approximation<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 16px;\"><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-dbf0ef5be3e2a7fc39d609f4621d2dbd_l3.png\" height=\"16\" width=\"113\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#66;&#92;&#97;&#112;&#112;&#114;&#111;&#120;&#32;&#88;&#32;&#92;&#99;&#111;&#108;&#111;&#110;&#101;&#113;&#113;&#32;&#81;&#67;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>It is easy to upgrade <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-eaad8e3728a66a376f3dee85dd42995a_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#88;&#32;&#61;&#32;&#81;&#67;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"68\" style=\"vertical-align: -4px;\"\/> into a <a href=\"https:\/\/en.m.wikipedia.org\/wiki\/Singular_value_decomposition#Compact_SVD\">compact SVD<\/a> form <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-97a583cd8dec13985b2fcde78223386b_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#88;&#32;&#61;&#32;&#85;&#92;&#83;&#105;&#103;&#109;&#97;&#32;&#86;&#94;&#42;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"87\" style=\"vertical-align: 0px;\"\/>, as we did as steps 4 and 5 in the previous post.<\/p>\n\n\n\n<p>For the analysis of the randomized SVD, it is helpful to notice that the approximation <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-ee8974e4adfbdab75fa43f4df80b4e5d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#88;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"16\" style=\"vertical-align: 0px;\"\/> takes the form<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 18px;\"><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-0d1ae78fbe7d6d4d91b567795bd91f57_l3.png\" height=\"18\" width=\"219\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#88;&#32;&#61;&#32;&#81;&#67;&#32;&#61;&#32;&#81;&#81;&#94;&#42;&#66;&#32;&#61;&#32;&#92;&#80;&#105;&#95;&#123;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#125;&#32;&#66;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>Here, <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-97a5221bf9d9b98b1d4a78bbf2e27a3f_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#80;&#105;&#95;&#123;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"34\" style=\"vertical-align: -3px;\"\/> denotes the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Projection_(linear_algebra)#Orthogonal_projections\">orthogonal projection<\/a> onto the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Row_and_column_spaces\">column space<\/a> of the matrix <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-f9d3279787c12e70cfc58fab42769995_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#66;&#92;&#79;&#109;&#101;&#103;&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"26\" style=\"vertical-align: 0px;\"\/>. We call <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-c191841ee3951abc042b4e58f27d65e3_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#88;&#32;&#61;&#32;&#92;&#80;&#105;&#95;&#123;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#125;&#32;&#66;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"89\" style=\"vertical-align: -3px;\"\/> the <em>projection formula<\/em> for the randomized SVD.<sup class=\"modern-footnotes-footnote \" data-mfn=\"1\" data-mfn-post-scope=\"000000000000057f0000000000000000_1529\"><a href=\"javascript:void(0)\"  role=\"button\" aria-pressed=\"false\" aria-describedby=\"mfn-content-000000000000057f0000000000000000_1529-1\">1<\/a><\/sup><span id=\"mfn-content-000000000000057f0000000000000000_1529-1\" role=\"tooltip\" class=\"modern-footnotes-footnote__note\" tabindex=\"0\" data-mfn=\"1\">This formula bares a good deal of similarity to the <a href=\"https:\/\/www.ethanepperly.com\/index.php\/2022\/10\/11\/low-rank-approximation-toolbox-nystrom-approximation\/\">projection formula for the Nystr\u00f6m approximation<\/a>. This is not a coincidence.<\/span>\n\n\n\n<h2 class=\"wp-block-heading\">Aside: Quadratic <a href=\"https:\/\/nhigham.com\/2021\/02\/02\/what-is-a-unitarily-invariant-norm\/\">Unitarily Invariant Norms<\/a><\/h2>\n\n\n\n<p>To state our error bounds in the most general language, we can adopt the language of <em>quadratic <a href=\"https:\/\/nhigham.com\/2021\/02\/02\/what-is-a-unitarily-invariant-norm\/\">unitarily invariant<\/a> norms<\/em>. Recall that a square matrix <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-c7480669f4fca8a251671d27137d0b09_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#85;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"13\" style=\"vertical-align: 0px;\"\/> is <em><a href=\"https:\/\/en.wikipedia.org\/wiki\/Unitary_matrix\">unitary<\/a><\/em> if<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 14px;\"><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-33fedf7ef9e12832ea6188011e3874bd_l3.png\" height=\"14\" width=\"131\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#85;&#94;&#42;&#85;&#32;&#61;&#32;&#85;&#85;&#94;&#42;&#32;&#61;&#32;&#73;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>You may recall from <a href=\"https:\/\/www.ethanepperly.com\/index.php\/2022\/10\/11\/low-rank-approximation-toolbox-nystrom-approximation\/\">my post on Nystr\u00f6m approximation<\/a> that a norm <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-abf50ae9bad3b75e024229c18701f68b_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#99;&#100;&#111;&#116;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"36\" style=\"vertical-align: -5px;\"\/> on matrices is <a href=\"https:\/\/nhigham.com\/2021\/02\/02\/what-is-a-unitarily-invariant-norm\/\"><em>unitarily invariant<\/em><\/a> if<\/p>\n\n\n\n<p><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-5fd16f43277f7e25ee2f910665984e09_l3.png\" height=\"19\" width=\"541\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#85;&#66;&#86;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;&#32;&#61;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#66;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;&#32;&#92;&#113;&#117;&#97;&#100;&#32;&#92;&#116;&#101;&#120;&#116;&#123;&#102;&#111;&#114;&#32;&#97;&#108;&#108;&#32;&#117;&#110;&#105;&#116;&#97;&#114;&#121;&#32;&#109;&#97;&#116;&#114;&#105;&#99;&#101;&#115;&#32;&#36;&#85;&#36;&#44;&#32;&#36;&#86;&#36;&#32;&#97;&#110;&#100;&#32;&#97;&#110;&#121;&#32;&#109;&#97;&#116;&#114;&#105;&#120;&#32;&#36;&#66;&#36;&#125;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>A unitarily invariant norm <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-3cff2313d3200a1fe39d0c99592d4a79_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#99;&#100;&#111;&#116;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"22\" width=\"31\" style=\"vertical-align: -8px;\"\/> is said to be <em>quadratic<\/em> if there exists another unitarily invariant norm <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-abf50ae9bad3b75e024229c18701f68b_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#99;&#100;&#111;&#116;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"36\" style=\"vertical-align: -5px;\"\/> such that<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 25px;\"><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-aac3c6aec691fb438adf6690682d855d_l3.png\" height=\"25\" width=\"400\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#66;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#94;&#50;&#32;&#61;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#66;&#94;&#42;&#66;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;&#32;&#61;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#66;&#66;&#94;&#42;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;&#32;&#92;&#113;&#117;&#97;&#100;&#32;&#92;&#116;&#101;&#120;&#116;&#123;&#102;&#111;&#114;&#32;&#101;&#118;&#101;&#114;&#121;&#32;&#109;&#97;&#116;&#114;&#105;&#120;&#32;&#36;&#66;&#36;&#46;&#125;&#32;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>Many examples of quadratic unitarily invariant norms are found among the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Matrix_norm#Schatten_norms\">Schatten<\/a> <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-726e7ac82690902493102f577788aa40_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#112;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"10\" style=\"vertical-align: -4px;\"\/>-norms, defined as<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 38px;\"><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-d032386a33d5df74c8a44235dafac359_l3.png\" height=\"38\" width=\"157\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#66;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#83;&#95;&#112;&#125;&#94;&#112;&#32;&#92;&#99;&#111;&#108;&#111;&#110;&#101;&#113;&#113;&#32;&#92;&#115;&#117;&#109;&#95;&#105;&#32;&#92;&#115;&#105;&#103;&#109;&#97;&#95;&#105;&#40;&#66;&#41;&#94;&#112;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>Here, <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-b167f4c54f23834e599964abe2c3d4d0_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#115;&#105;&#103;&#109;&#97;&#95;&#49;&#40;&#66;&#41;&#32;&#92;&#103;&#101;&#32;&#92;&#115;&#105;&#103;&#109;&#97;&#95;&#50;&#40;&#66;&#41;&#32;&#92;&#103;&#101;&#32;&#92;&#99;&#100;&#111;&#116;&#115;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"159\" style=\"vertical-align: -5px;\"\/> denote the decreasingly order <a href=\"https:\/\/en.wikipedia.org\/wiki\/Singular_value\">singular values<\/a> of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-06d2c1a5a171b6d7d9c5df87d123c5a4_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#66;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/>. The Schatten <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-b5fed14f2144ce9f7a2e7c6c1a9858d9_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#50;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"8\" style=\"vertical-align: 0px;\"\/>-norm <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-6a0788a03a084a56037243725221df66_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#99;&#100;&#111;&#116;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#83;&#95;&#50;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"21\" width=\"35\" style=\"vertical-align: -7px;\"\/> is the <em><a href=\"https:\/\/en.wikipedia.org\/wiki\/Matrix_norm#Frobenius_norm\">Frobenius norm<\/a><\/em> of a matrix. The <em><a href=\"https:\/\/en.wikipedia.org\/wiki\/Matrix_norm#Matrix_norms_induced_by_vector_p-norms\">spectral norm<\/a><\/em> (i.e., operator 2-norm) is the Schatten <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-9f9e97344403ddcf19e9a85e05b98b52_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#105;&#110;&#102;&#116;&#121;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"17\" style=\"vertical-align: 0px;\"\/>-norm, defined to be<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 25px;\"><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-584051e6c083d9b865ffe52d79186a00_l3.png\" height=\"25\" width=\"289\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#110;&#111;&#114;&#109;&#123;&#66;&#125;&#32;&#61;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#66;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#83;&#95;&#92;&#105;&#110;&#102;&#116;&#121;&#125;&#32;&#92;&#99;&#111;&#108;&#111;&#110;&#101;&#113;&#113;&#32;&#92;&#109;&#97;&#120;&#95;&#105;&#32;&#92;&#115;&#105;&#103;&#109;&#97;&#95;&#105;&#40;&#66;&#41;&#32;&#61;&#32;&#92;&#115;&#105;&#103;&#109;&#97;&#95;&#49;&#40;&#66;&#41;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>The Schatten <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-726e7ac82690902493102f577788aa40_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#112;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"10\" style=\"vertical-align: -4px;\"\/>-norms are unitarily invariant norms for every <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-3adc612129d031177ed3d74c73ff13d6_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#49;&#92;&#108;&#101;&#32;&#112;&#32;&#92;&#108;&#101;&#32;&#92;&#105;&#110;&#102;&#116;&#121;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"81\" style=\"vertical-align: -4px;\"\/>. However, the Schatten <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-726e7ac82690902493102f577788aa40_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#112;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"10\" style=\"vertical-align: -4px;\"\/>-norms are <em>quadratic unitarily invariant norms<\/em> only for <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-4d8228a94e5502dd5d7da29647407804_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#50;&#92;&#108;&#101;&#32;&#112;&#32;&#92;&#108;&#101;&#32;&#92;&#105;&#110;&#102;&#116;&#121;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"82\" style=\"vertical-align: -4px;\"\/> since<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 28px;\"><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-27e888ecff0b0c38df6e73a803f8aa1d_l3.png\" height=\"28\" width=\"159\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#66;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#83;&#95;&#112;&#125;&#94;&#50;&#32;&#61;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#66;&#94;&#42;&#66;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#83;&#95;&#123;&#112;&#47;&#50;&#125;&#125;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>For the remainder of this post, we let <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-3cff2313d3200a1fe39d0c99592d4a79_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#99;&#100;&#111;&#116;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"22\" width=\"31\" style=\"vertical-align: -8px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-abf50ae9bad3b75e024229c18701f68b_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#99;&#100;&#111;&#116;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"36\" style=\"vertical-align: -5px;\"\/> be a quadratic unitarily invariant norm pair satisfying (1).<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Error Decomposition<\/h2>\n\n\n\n<p>The starting point of our analysis is the following decomposition of the error of the randomized SVD:<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 26px;\"><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-c1738a10a5c46d5455b8e2d5992ce98d_l3.png\" height=\"26\" width=\"394\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#66;&#32;&#45;&#32;&#88;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#94;&#50;&#32;&#92;&#108;&#101;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#66;&#32;&#45;&#32;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#94;&#50;&#32;&#43;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#32;&#45;&#32;&#92;&#80;&#105;&#95;&#123;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#125;&#32;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#94;&#50;&#46;&#32;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>Recall that we have defined <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-ffe0e3fd4e435705f3d70971e5f2952d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;\" title=\"Rendered by QuickLaTeX.com\" height=\"18\" width=\"33\" style=\"vertical-align: -5px;\"\/> to be an optimal rank-<img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-0cfb382a93bc3f68981565d49d1aeb9e_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#114;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"8\" style=\"vertical-align: 0px;\"\/> approximation to <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-06d2c1a5a171b6d7d9c5df87d123c5a4_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#66;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/>:<\/p>\n\n\n\n<p><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-46106e1ebeaa349721ea4e81d171f70b_l3.png\" height=\"23\" width=\"415\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#66;&#32;&#45;&#32;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#114;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#32;&#92;&#108;&#101;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#66;&#32;&#45;&#32;&#67;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#32;&#92;&#113;&#117;&#97;&#100;&#32;&#92;&#116;&#101;&#120;&#116;&#123;&#102;&#111;&#114;&#32;&#97;&#110;&#121;&#32;&#114;&#97;&#110;&#107;&#45;&#36;&#114;&#36;&#32;&#109;&#97;&#116;&#114;&#105;&#120;&#32;&#36;&#67;&#36;&#125;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>Thus, the error decomposition says that the <em>excess error<\/em> is bounded by<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 26px;\"><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-e44e6de74ec072bf3d6c944ea6de77db_l3.png\" height=\"26\" width=\"394\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#66;&#32;&#45;&#32;&#88;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#94;&#50;&#32;&#45;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#66;&#32;&#45;&#32;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#94;&#50;&#32;&#92;&#108;&#101;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#32;&#45;&#32;&#92;&#80;&#105;&#95;&#123;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#125;&#32;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#94;&#50;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>Using the projection formula, we can prove the error decomposition (2) directly:<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 171px;\"><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-78e61c64010d724a040c22335ea173ae_l3.png\" height=\"171\" width=\"452\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#98;&#101;&#103;&#105;&#110;&#123;&#97;&#108;&#105;&#103;&#110;&#42;&#125;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#66;&#32;&#45;&#32;&#88;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#94;&#50;&#32;&#38;&#61;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#66;&#32;&#45;&#32;&#92;&#80;&#105;&#95;&#123;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#125;&#32;&#66;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#94;&#50;&#92;&#92;&#38;&#61;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#40;&#73;&#45;&#92;&#80;&#105;&#95;&#123;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#125;&#41;&#66;&#66;&#94;&#42;&#40;&#73;&#45;&#92;&#80;&#105;&#95;&#123;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#125;&#41;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;&#32;&#92;&#92;&#38;&#92;&#108;&#101;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#40;&#73;&#45;&#92;&#80;&#105;&#95;&#123;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#125;&#41;&#40;&#66;&#66;&#94;&#42;&#32;&#45;&#32;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#94;&#42;&#41;&#40;&#73;&#45;&#92;&#80;&#105;&#95;&#123;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#125;&#41;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;&#32;&#92;&#92;&#38;&#92;&#113;&#113;&#117;&#97;&#100;&#32;&#43;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#40;&#73;&#45;&#92;&#80;&#105;&#95;&#123;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#125;&#41;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#94;&#42;&#40;&#73;&#45;&#92;&#80;&#105;&#95;&#123;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#125;&#41;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;&#92;&#92;&#38;&#92;&#108;&#101;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#66;&#66;&#94;&#42;&#32;&#45;&#32;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#94;&#42;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;&#32;&#43;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#32;&#45;&#32;&#92;&#80;&#105;&#95;&#123;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#125;&#32;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#94;&#50;&#32;&#92;&#92;&#38;&#92;&#108;&#101;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#66;&#32;&#45;&#32;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#94;&#50;&#32;&#43;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#45;&#32;&#92;&#80;&#105;&#95;&#123;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#125;&#32;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#94;&#50;&#46;&#92;&#101;&#110;&#100;&#123;&#97;&#108;&#105;&#103;&#110;&#42;&#125;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>The first line is the projection formula, the second is relation between <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-6771c54dbdaccbbfa2860d1206c049fa_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#110;&#111;&#114;&#109;&#123;&#92;&#99;&#100;&#111;&#116;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"22\" width=\"31\" style=\"vertical-align: -8px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-1bfad97a2db8d66076bf7257de4a4b23_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#110;&#111;&#114;&#109;&#123;&#92;&#99;&#100;&#111;&#116;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"36\" style=\"vertical-align: -5px;\"\/>, and the third is the triangle inequality. For the fifth line, we use the fact that <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-43429bb8e2ec53b848ee953f4b4d11b4_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#73;&#32;&#45;&#32;&#92;&#80;&#105;&#95;&#123;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"65\" style=\"vertical-align: -3px;\"\/> is an orthoprojector and thus has unit spectral norm <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-319f44f36e97b4cd434fbbd56aec1c46_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#110;&#111;&#114;&#109;&#123;&#73;&#32;&#45;&#32;&#92;&#80;&#105;&#95;&#123;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#125;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"80\" style=\"vertical-align: -5px;\"\/> together with the fact that<\/p>\n\n\n\n<p><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-e329f332e4305af288668bfdf1ab4bf5_l3.png\" height=\"19\" width=\"443\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#66;&#67;&#68;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;&#32;&#92;&#108;&#101;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#66;&#125;&#32;&#92;&#99;&#100;&#111;&#116;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#67;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;&#92;&#99;&#100;&#111;&#116;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#68;&#125;&#32;&#92;&#113;&#117;&#97;&#100;&#32;&#92;&#116;&#101;&#120;&#116;&#123;&#102;&#111;&#114;&#32;&#97;&#108;&#108;&#32;&#109;&#97;&#116;&#114;&#105;&#99;&#101;&#115;&#32;&#36;&#66;&#44;&#67;&#44;&#68;&#36;&#46;&#125;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>For the final inequality, we used commutation rule<\/p>\n\n\n\n<p><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-9db3f7e6eb57261b556783a0a7d62fd0_l3.png\" height=\"19\" width=\"342\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#40;&#66;&#32;&#45;&#32;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#41;&#40;&#66;&#32;&#45;&#32;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#41;&#94;&#42;&#32;&#61;&#32;&#66;&#66;&#94;&#42;&#32;&#45;&#32;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#94;&#42;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Bounding the Error<\/h2>\n\n\n\n<p>In this section, we shall continue to refine the error decomposition (2). Consider a <a href=\"https:\/\/en.wikipedia.org\/wiki\/Singular_value_decomposition#Thin_SVD\">thin SVD<\/a> of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-06d2c1a5a171b6d7d9c5df87d123c5a4_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#66;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/>, partitioned as<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 42px;\"><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-54a749c18b5a76a0f468adee8b5fa58f_l3.png\" height=\"42\" width=\"264\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#66;&#32;&#61;&#32;&#92;&#111;&#110;&#101;&#98;&#121;&#116;&#119;&#111;&#123;&#85;&#95;&#49;&#125;&#123;&#85;&#95;&#50;&#125;&#32;&#92;&#116;&#119;&#111;&#98;&#121;&#116;&#119;&#111;&#123;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#125;&#123;&#48;&#125;&#123;&#48;&#125;&#123;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#125;&#92;&#111;&#110;&#101;&#98;&#121;&#116;&#119;&#111;&#123;&#86;&#95;&#49;&#125;&#123;&#86;&#95;&#50;&#125;&#94;&#42;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>where<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-310d0549553f63221e3533e54010134a_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#111;&#110;&#101;&#98;&#121;&#116;&#119;&#111;&#123;&#85;&#95;&#49;&#125;&#123;&#85;&#95;&#50;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"22\" width=\"64\" style=\"vertical-align: -7px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-c721348dfa3f03a445a52990c9d7cc99_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#111;&#110;&#101;&#98;&#121;&#116;&#119;&#111;&#123;&#86;&#95;&#49;&#125;&#123;&#86;&#95;&#50;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"22\" width=\"61\" style=\"vertical-align: -7px;\"\/> both have orthonormal columns,<\/li>\n\n\n\n<li><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-aceeae0de9b43ecefade254732018e34_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"19\" style=\"vertical-align: -3px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-d6aac687f4bc5a57b6b0b5527d920e60_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"20\" style=\"vertical-align: -3px;\"\/> are square diagonal matrices with nonnegative entries,<\/li>\n\n\n\n<li><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-dc130d2b6546bc8a7eedb1c5d5e45a50_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#85;&#95;&#49;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"17\" style=\"vertical-align: -3px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-522a258f93266e7b364409f16ddfaa68_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#86;&#95;&#49;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"16\" style=\"vertical-align: -3px;\"\/> have <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-0cfb382a93bc3f68981565d49d1aeb9e_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#114;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"8\" style=\"vertical-align: 0px;\"\/> columns, and<\/li>\n\n\n\n<li><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-aceeae0de9b43ecefade254732018e34_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"19\" style=\"vertical-align: -3px;\"\/> is an <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-d54a1ffcb24a8633fec3aa15bc6e3de0_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#114;&#92;&#116;&#105;&#109;&#101;&#115;&#32;&#114;\" title=\"Rendered by QuickLaTeX.com\" height=\"9\" width=\"38\" style=\"vertical-align: 0px;\"\/> matrix.<\/li>\n<\/ul>\n\n\n\n<p>Under this notation, the best rank-<img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-0cfb382a93bc3f68981565d49d1aeb9e_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#114;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"8\" style=\"vertical-align: 0px;\"\/> approximation is <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-da3890d8280a7eb0664650278fc6f047_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#32;&#61;&#32;&#85;&#95;&#49;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#86;&#95;&#49;&#94;&#42;\" title=\"Rendered by QuickLaTeX.com\" height=\"18\" width=\"118\" style=\"vertical-align: -5px;\"\/>. Define<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 42px;\"><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-f620ec79bd8a3f6022efb5ca07b0d824_l3.png\" height=\"42\" width=\"123\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#116;&#119;&#111;&#98;&#121;&#111;&#110;&#101;&#123;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#125;&#123;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#50;&#125;&#32;&#92;&#99;&#111;&#108;&#111;&#110;&#101;&#113;&#113;&#32;&#92;&#116;&#119;&#111;&#98;&#121;&#111;&#110;&#101;&#123;&#86;&#95;&#49;&#94;&#42;&#125;&#123;&#86;&#95;&#50;&#94;&#42;&#125;&#32;&#92;&#79;&#109;&#101;&#103;&#97;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>We assume throughout that <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-8054fed550f38ce14b26d47a239efccc_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"19\" style=\"vertical-align: -3px;\"\/> is full-rank (i.e., <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-6a8ad642fa4ec335f191df677cb8765c_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#111;&#112;&#101;&#114;&#97;&#116;&#111;&#114;&#110;&#97;&#109;&#101;&#123;&#114;&#97;&#110;&#107;&#125;&#32;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#32;&#61;&#32;&#114;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"90\" style=\"vertical-align: -3px;\"\/>).<\/p>\n\n\n\n<p>Applying the error decomposition (2), we get<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 83px;\"><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-7b8e6eab799862389a8ff0ab6eaf56ef_l3.png\" height=\"83\" width=\"541\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#98;&#101;&#103;&#105;&#110;&#123;&#97;&#108;&#105;&#103;&#110;&#42;&#125;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#66;&#32;&#45;&#32;&#88;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#94;&#50;&#38;&#92;&#108;&#101;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#32;&#92;&#111;&#110;&#101;&#98;&#121;&#116;&#119;&#111;&#123;&#85;&#95;&#49;&#125;&#123;&#85;&#95;&#50;&#125;&#32;&#92;&#116;&#119;&#111;&#98;&#121;&#116;&#119;&#111;&#123;&#48;&#125;&#123;&#48;&#125;&#123;&#48;&#125;&#123;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#125;&#92;&#111;&#110;&#101;&#98;&#121;&#116;&#119;&#111;&#123;&#86;&#95;&#49;&#125;&#123;&#86;&#95;&#50;&#125;&#94;&#42;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#94;&#50;&#32;&#43;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#40;&#73;&#45;&#92;&#80;&#105;&#95;&#123;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#125;&#41;&#85;&#95;&#49;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#86;&#95;&#49;&#94;&#42;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#94;&#50;&#32;&#92;&#92;&#38;&#61;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#32;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#94;&#50;&#32;&#43;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#40;&#73;&#45;&#92;&#80;&#105;&#95;&#123;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#125;&#41;&#85;&#95;&#49;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#94;&#50;&#46;&#32;&#92;&#101;&#110;&#100;&#123;&#97;&#108;&#105;&#103;&#110;&#42;&#125;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>For the second line, we used the unitary invariance of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-3cff2313d3200a1fe39d0c99592d4a79_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#99;&#100;&#111;&#116;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"22\" width=\"31\" style=\"vertical-align: -8px;\"\/>. Observe that the column space of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-f9d3279787c12e70cfc58fab42769995_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#66;&#92;&#79;&#109;&#101;&#103;&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"26\" style=\"vertical-align: 0px;\"\/> is a superset of the column space of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-7d195e0d766fb22183991fe696303bc3_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;\" title=\"Rendered by QuickLaTeX.com\" height=\"23\" width=\"46\" style=\"vertical-align: -5px;\"\/> so<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 40px;\"><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-2fdd85edd3e561ae5496031960d8901a_l3.png\" height=\"40\" width=\"584\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#110;&#111;&#114;&#109;&#123;&#40;&#73;&#45;&#92;&#80;&#105;&#95;&#123;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#125;&#41;&#85;&#95;&#49;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#94;&#50;&#32;&#92;&#108;&#101;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#40;&#73;&#45;&#92;&#80;&#105;&#95;&#123;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#125;&#41;&#85;&#95;&#49;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#94;&#50;&#32;&#61;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#85;&#95;&#49;&#94;&#42;&#40;&#73;&#45;&#92;&#80;&#105;&#95;&#123;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#125;&#41;&#85;&#95;&#49;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;&#46;&#32;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>Let&#8217;s work on simplifying the expression<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 25px;\"><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-f21f88902abb8532d54b098fa358ddc0_l3.png\" height=\"25\" width=\"183\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#85;&#95;&#49;&#94;&#42;&#40;&#73;&#45;&#92;&#80;&#105;&#95;&#123;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#125;&#41;&#85;&#95;&#49;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>First, observe that<\/p>\n\n\n\n<p><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-e1dbcff75c12101b6274492896899b52_l3.png\" height=\"43\" width=\"620\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#61;&#32;&#66;&#92;&#111;&#110;&#101;&#98;&#121;&#116;&#119;&#111;&#123;&#86;&#95;&#49;&#125;&#123;&#86;&#95;&#50;&#125;&#92;&#116;&#119;&#111;&#98;&#121;&#111;&#110;&#101;&#123;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#125;&#123;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#50;&#125;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#61;&#32;&#92;&#111;&#110;&#101;&#98;&#121;&#116;&#119;&#111;&#123;&#85;&#95;&#49;&#125;&#123;&#85;&#95;&#50;&#125;&#32;&#92;&#116;&#119;&#111;&#98;&#121;&#116;&#119;&#111;&#123;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#125;&#123;&#48;&#125;&#123;&#48;&#125;&#123;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#125;&#32;&#92;&#116;&#119;&#111;&#98;&#121;&#111;&#110;&#101;&#123;&#73;&#125;&#123;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#125;&#32;&#61;&#32;&#85;&#95;&#49;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#32;&#43;&#32;&#85;&#95;&#50;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p><a href=\"https:\/\/en.wikipedia.org\/wiki\/Projection_(linear_algebra)#Formulas\">Thus<\/a>, the projector <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-491b9094fd9b4e87c6bf46260b5f0fb5_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#80;&#105;&#95;&#123;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"23\" width=\"49\" style=\"vertical-align: -11px;\"\/> takes the form<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 78px;\"><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-d9e0cd585357787c460f6471f52ecb0a_l3.png\" height=\"78\" width=\"632\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#98;&#101;&#103;&#105;&#110;&#123;&#97;&#108;&#105;&#103;&#110;&#42;&#125;&#92;&#80;&#105;&#95;&#123;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#125;&#32;&#38;&#61;&#32;&#40;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#41;&#32;&#92;&#108;&#101;&#102;&#116;&#091;&#40;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#41;&#94;&#42;&#40;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#41;&#92;&#114;&#105;&#103;&#104;&#116;&#093;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#40;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#41;&#94;&#42;&#32;&#92;&#92;&#38;&#61;&#32;&#40;&#85;&#95;&#49;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#32;&#43;&#32;&#85;&#95;&#50;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#41;&#32;&#92;&#108;&#101;&#102;&#116;&#091;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#94;&#50;&#32;&#43;&#32;&#40;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#41;&#94;&#42;&#40;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#41;&#92;&#114;&#105;&#103;&#104;&#116;&#093;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#40;&#85;&#95;&#49;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#32;&#43;&#32;&#85;&#95;&#50;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#41;&#94;&#42;&#46;&#92;&#101;&#110;&#100;&#123;&#97;&#108;&#105;&#103;&#110;&#42;&#125;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>Here, <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-9c3eba346ed7d1ef93cd5446d6845382_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#123;&#125;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"6\" style=\"vertical-align: 3px;\"\/> denotes the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Moore\u2013Penrose_inverse\">Moore\u2013Penrose pseudoinverse<\/a>, which reduces to the ordinary matrix inverse for a <a href=\"https:\/\/en.wikipedia.org\/wiki\/Invertible_matrix\">square nonsingular matrix<\/a>. Thus,<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 36px;\"><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-b7dfa3f3cbcda5380b6b7ec0132fca2a_l3.png\" height=\"36\" width=\"519\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#85;&#95;&#49;&#94;&#42;&#40;&#73;&#45;&#92;&#80;&#105;&#95;&#123;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#125;&#41;&#85;&#95;&#49;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#32;&#61;&#32;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#94;&#50;&#32;&#45;&#32;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#94;&#50;&#32;&#92;&#108;&#101;&#102;&#116;&#091;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#94;&#50;&#32;&#43;&#32;&#40;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#41;&#94;&#42;&#40;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#41;&#92;&#114;&#105;&#103;&#104;&#116;&#093;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#94;&#50;&#46;&#32;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>Remarkably, this seemingly convoluted combination of matrices actually is a well-studied operation in matrix theory, the <em><a href=\"https:\/\/doi.org\/10.1016\/0022-247X(69)90200-5\">parallel sum<\/a><\/em>. The parallel sum of <a href=\"https:\/\/en.wikipedia.org\/wiki\/Definite_matrix#Definitions_for_complex_matrices\">positive semidefinite matrices<\/a> <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;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-c5f986724262f699e22a9dfc5cb767a6_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#72;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"16\" style=\"vertical-align: 0px;\"\/> is defined as<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 22px;\"><span class=\"ql-right-eqno\"> (6) <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-0ca6dd2810aa560e0d59d808c9b40bc8_l3.png\" height=\"22\" width=\"209\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#65;&#32;&#58;&#32;&#72;&#32;&#92;&#99;&#111;&#108;&#111;&#110;&#101;&#113;&#113;&#32;&#65;&#32;&#45;&#32;&#65;&#40;&#65;&#43;&#72;&#41;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#65;&#46;&#32;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>We will have much more to say about the parallel sum soon. For now, we use this notation to rewrite (5) as<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 29px;\"><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-dc620e38c4fb8a7855e330183c8313c9_l3.png\" height=\"29\" width=\"410\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#85;&#95;&#49;&#94;&#42;&#40;&#73;&#45;&#92;&#80;&#105;&#95;&#123;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#125;&#41;&#85;&#95;&#49;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#32;&#61;&#32;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#94;&#50;&#32;&#58;&#32;&#091;&#40;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#41;&#94;&#42;&#40;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#41;&#093;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>Plugging this back into (4) and then (3), we obtain the error bound<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 34px;\"><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-ff8a161c38344c97e0d615d216d4555d_l3.png\" height=\"34\" width=\"421\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#66;&#32;&#45;&#32;&#88;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#94;&#50;&#92;&#108;&#101;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#32;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#94;&#50;&#32;&#43;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#94;&#50;&#32;&#58;&#32;&#091;&#40;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#41;&#94;&#42;&#40;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#41;&#093;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;&#46;&#32;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>Simplifying this expression further will require more knowledge about parallel sums, which we shall discuss now.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Aside: <a href=\"https:\/\/doi.org\/10.1016\/0022-247X(69)90200-5\">Parallel Sums<\/a><\/h2>\n\n\n\n<p>Let us put aside the randomized SVD for a moment and digress to the seemingly unrelated topic of <a href=\"https:\/\/en.wikipedia.org\/wiki\/Series_and_parallel_circuits\">electrical circuits<\/a>. Suppose we have a battery of <a href=\"https:\/\/en.wikipedia.org\/wiki\/Voltage#Circuit_theory\">voltage<\/a> <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-1ccb53cb35fc73370b29b241e3fa4bcd_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#118;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"9\" style=\"vertical-align: 0px;\"\/> and we connect the ends using a wire of <a href=\"https:\/\/en.wikipedia.org\/wiki\/Electrical_resistance_and_conductance\">resistance<\/a> <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-a75c3139cf459f4de0ac69cfbed08a4c_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"9\" style=\"vertical-align: 0px;\"\/>. The <a href=\"https:\/\/en.wikipedia.org\/wiki\/Electric_current\">current<\/a> <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-34a31a1dd2fec9fc6bf0c85d1a13d9ec_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#109;&#97;&#116;&#104;&#114;&#109;&#123;&#99;&#117;&#114;&#114;&#125;&#95;&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"11\" width=\"39\" style=\"vertical-align: -3px;\"\/> is given by <a href=\"https:\/\/en.wikipedia.org\/wiki\/Ohm%27s_law\">Ohm&#8217;s law<\/a><\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 10px;\"><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-50ff6a1f099e535f6dfd8525f45b4741_l3.png\" height=\"10\" width=\"99\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#118;&#32;&#61;&#32;&#97;&#32;&#92;&#99;&#100;&#111;&#116;&#32;&#92;&#109;&#97;&#116;&#104;&#114;&#109;&#123;&#99;&#117;&#114;&#114;&#125;&#95;&#97;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>Similarly, if the wire is replaced by a different wire with resistance <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-471140fbd20a10d0f411d52aa20652e4_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#104;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"10\" style=\"vertical-align: 0px;\"\/>, the current <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-ee02a88a5c6b451ec475cc752e28e90a_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#109;&#97;&#116;&#104;&#114;&#109;&#123;&#99;&#117;&#114;&#114;&#125;&#95;&#104;\" title=\"Rendered by QuickLaTeX.com\" height=\"11\" width=\"40\" style=\"vertical-align: -3px;\"\/> is then<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 15px;\"><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-baea64abba5be2425a04d7d2316f7153_l3.png\" height=\"15\" width=\"100\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#118;&#32;&#61;&#32;&#104;&#32;&#92;&#99;&#100;&#111;&#116;&#32;&#92;&#109;&#97;&#116;&#104;&#114;&#109;&#123;&#99;&#117;&#114;&#114;&#125;&#95;&#104;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>Now comes the interesting question. What if we connect the battery by <em>both<\/em> wires (resistances <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-a75c3139cf459f4de0ac69cfbed08a4c_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"9\" style=\"vertical-align: 0px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-471140fbd20a10d0f411d52aa20652e4_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#104;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"10\" style=\"vertical-align: 0px;\"\/>) simultaneously <a href=\"https:\/\/en.wikipedia.org\/wiki\/Series_and_parallel_circuits#Parallel_circuits\"><em>in parallel<\/em><\/a>, so that current can flow through either wire? Since wires of resistances <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-a75c3139cf459f4de0ac69cfbed08a4c_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"9\" style=\"vertical-align: 0px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-471140fbd20a10d0f411d52aa20652e4_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#104;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"10\" style=\"vertical-align: 0px;\"\/> still have voltage <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-1ccb53cb35fc73370b29b241e3fa4bcd_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#118;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"9\" style=\"vertical-align: 0px;\"\/>, Ohm&#8217;s law still applies and thus the total current is<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 32px;\"><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-2ce6cd66280641977f8eea4d3d9f6cab_l3.png\" height=\"32\" width=\"396\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#109;&#97;&#116;&#104;&#114;&#109;&#123;&#99;&#117;&#114;&#114;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#116;&#111;&#116;&#97;&#108;&#125;&#32;&#61;&#32;&#92;&#109;&#97;&#116;&#104;&#114;&#109;&#123;&#99;&#117;&#114;&#114;&#125;&#95;&#97;&#32;&#43;&#32;&#92;&#109;&#97;&#116;&#104;&#114;&#109;&#123;&#99;&#117;&#114;&#114;&#125;&#95;&#104;&#32;&#61;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#118;&#125;&#123;&#97;&#125;&#32;&#43;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#118;&#125;&#123;&#104;&#125;&#32;&#61;&#32;&#118;&#32;&#92;&#108;&#101;&#102;&#116;&#40;&#97;&#94;&#123;&#45;&#49;&#125;&#43;&#104;&#94;&#123;&#45;&#49;&#125;&#92;&#114;&#105;&#103;&#104;&#116;&#41;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>The net effect of connecting resisting wires of resistances <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-a75c3139cf459f4de0ac69cfbed08a4c_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"9\" style=\"vertical-align: 0px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-471140fbd20a10d0f411d52aa20652e4_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#104;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"10\" style=\"vertical-align: 0px;\"\/> is <a href=\"https:\/\/en.wikipedia.org\/wiki\/Series_and_parallel_circuits#Current_2\">the same as a single resisting wire of resistance<\/a><\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 35px;\"><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-46eba66bdf328c974e763d8c43422e75_l3.png\" height=\"35\" width=\"269\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#97;&#58;&#104;&#32;&#92;&#99;&#111;&#108;&#111;&#110;&#101;&#113;&#113;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#118;&#125;&#123;&#92;&#109;&#97;&#116;&#104;&#114;&#109;&#123;&#99;&#117;&#114;&#114;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#116;&#111;&#116;&#97;&#108;&#125;&#125;&#32;&#61;&#32;&#92;&#108;&#101;&#102;&#116;&#40;&#32;&#97;&#94;&#123;&#45;&#49;&#125;&#43;&#104;&#94;&#123;&#45;&#49;&#125;&#92;&#114;&#105;&#103;&#104;&#116;&#41;&#94;&#123;&#45;&#49;&#125;&#46;&#32;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>We call the the operation <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-b294224fb1b0ca6a1aaffa0a5b613992_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#97;&#32;&#92;&#109;&#97;&#116;&#104;&#98;&#105;&#110;&#123;&#58;&#125;&#32;&#104;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"32\" style=\"vertical-align: 0px;\"\/> the <em>parallel sum<\/em> of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-a75c3139cf459f4de0ac69cfbed08a4c_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"9\" style=\"vertical-align: 0px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-471140fbd20a10d0f411d52aa20652e4_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#104;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"10\" style=\"vertical-align: 0px;\"\/> because it describes how resistances combine when connected in parallel.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-medium\"><img loading=\"lazy\" decoding=\"async\" width=\"292\" height=\"300\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/uploads\/2023\/06\/circuits_parallel-292x300.png\" alt=\"\" class=\"wp-image-1546\" srcset=\"https:\/\/www.ethanepperly.com\/wp-content\/uploads\/2023\/06\/circuits_parallel-292x300.png 292w, https:\/\/www.ethanepperly.com\/wp-content\/uploads\/2023\/06\/circuits_parallel-998x1024.png 998w, https:\/\/www.ethanepperly.com\/wp-content\/uploads\/2023\/06\/circuits_parallel-768x788.png 768w, https:\/\/www.ethanepperly.com\/wp-content\/uploads\/2023\/06\/circuits_parallel.png 1420w\" sizes=\"auto, (max-width: 292px) 100vw, 292px\" \/><\/figure><\/div>\n\n\n<p>The parallel sum operation <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-e1e2555b43b06c03228ef832ba28bd77_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#58;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"3\" style=\"vertical-align: 0px;\"\/> can be extended to all <em>nonnegative<\/em> numbers <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-a75c3139cf459f4de0ac69cfbed08a4c_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"9\" style=\"vertical-align: 0px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-471140fbd20a10d0f411d52aa20652e4_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#104;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"10\" style=\"vertical-align: 0px;\"\/> by continuity:<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 54px;\"><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-7c49cbcbcd8d8f75fa4f18a40562e718_l3.png\" height=\"54\" width=\"399\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#97;&#58;&#104;&#32;&#92;&#99;&#111;&#108;&#111;&#110;&#101;&#113;&#113;&#32;&#92;&#108;&#105;&#109;&#95;&#123;&#98;&#92;&#100;&#111;&#119;&#110;&#97;&#114;&#114;&#111;&#119;&#32;&#97;&#44;&#32;&#92;&#58;&#32;&#107;&#92;&#100;&#111;&#119;&#110;&#97;&#114;&#114;&#111;&#119;&#32;&#104;&#125;&#32;&#98;&#58;&#107;&#32;&#61;&#32;&#92;&#98;&#101;&#103;&#105;&#110;&#123;&#99;&#97;&#115;&#101;&#115;&#125;&#92;&#108;&#101;&#102;&#116;&#40;&#32;&#97;&#94;&#123;&#45;&#49;&#125;&#43;&#104;&#94;&#123;&#45;&#49;&#125;&#92;&#114;&#105;&#103;&#104;&#116;&#41;&#94;&#123;&#45;&#49;&#125;&#44;&#32;&#38;&#32;&#97;&#44;&#104;&#32;&#62;&#32;&#48;&#32;&#44;&#92;&#92;&#48;&#44;&#32;&#38;&#32;&#92;&#116;&#101;&#120;&#116;&#114;&#109;&#123;&#111;&#116;&#104;&#101;&#114;&#119;&#105;&#115;&#101;&#125;&#46;&#92;&#101;&#110;&#100;&#123;&#99;&#97;&#115;&#101;&#115;&#125;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>Electrically, this definition states that one obtains a short circuit (resistance <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-54589d9b5610bf48dcf5a1b1f24a67b6_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#48;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: 0px;\"\/>) if either of the wires carries zero resistance.<\/p>\n\n\n\n<p>Parallel sums of matrices were introduced by <a href=\"https:\/\/orcid.org\/0000-0003-4204-3415\">William N. Anderson, Jr.<\/a> and <a href=\"https:\/\/en.wikipedia.org\/wiki\/Richard_Duffin\">Richard J. Duffin<\/a> as a generalization of the parallel sum operation from electrical circuits. There are several equivalent definitions. The natural definition (8) applies for <a href=\"https:\/\/en.wikipedia.org\/wiki\/Definite_matrix#Definitions_for_complex_matrices\"><em>positive definite matrices<\/em><\/a><\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 22px;\"><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-95cd7707ba37e3436926c73895d537bb_l3.png\" height=\"22\" width=\"404\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#65;&#58;&#72;&#32;&#61;&#32;&#40;&#65;&#94;&#123;&#45;&#49;&#125;&#43;&#72;&#94;&#123;&#45;&#49;&#125;&#41;&#94;&#123;&#45;&#49;&#125;&#32;&#92;&#113;&#117;&#97;&#100;&#32;&#92;&#116;&#101;&#120;&#116;&#123;&#102;&#111;&#114;&#32;&#36;&#65;&#44;&#72;&#36;&#32;&#112;&#111;&#115;&#105;&#116;&#105;&#118;&#101;&#32;&#100;&#101;&#102;&#105;&#110;&#105;&#116;&#101;&#46;&#125;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>This definition can be extended to positive <em>semi<\/em>definite matrices by continuity. It can be useful to have an explicit definition which applies even to positive semidefinite matrices. To do so, observe that the (scalar) parallel sum satisfies the identity<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 42px;\"><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-e4e355840ccdeb857cec59c1173cca5b_l3.png\" height=\"42\" width=\"490\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#97;&#58;&#104;&#32;&#61;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#49;&#125;&#123;&#97;&#94;&#123;&#45;&#49;&#125;&#43;&#104;&#94;&#123;&#45;&#49;&#125;&#125;&#32;&#61;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#97;&#104;&#125;&#123;&#97;&#43;&#104;&#125;&#32;&#61;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#97;&#40;&#97;&#43;&#104;&#41;&#45;&#97;&#94;&#50;&#125;&#123;&#97;&#43;&#104;&#125;&#32;&#61;&#32;&#97;&#32;&#45;&#32;&#97;&#40;&#97;&#43;&#104;&#41;&#94;&#123;&#45;&#49;&#125;&#97;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>To extend to matrices, we capitalize the letters and use the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Moore\u2013Penrose_inverse\">Moore\u2013Penrose pseudoinverse<\/a> in place of the inverse:<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 22px;\"><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-85f7337339efbd593339ed3a5ff7e547_l3.png\" height=\"22\" width=\"205\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#65;&#32;&#58;&#32;&#72;&#32;&#61;&#32;&#65;&#32;&#45;&#32;&#65;&#40;&#65;&#43;&#72;&#41;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#65;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>This was the definition (6) of the parallel sum we gave above which we found naturally in our randomized SVD error bounds.<\/p>\n\n\n\n<p>The parallel sum enjoys a number of beautiful properties, some of which we list here:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Symmetry.<\/strong> <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-1754be6047979d2c20cbbf2bcb03d60b_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;&#58;&#72;&#32;&#61;&#32;&#72;&#58;&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"112\" style=\"vertical-align: 0px;\"\/>,<\/li>\n\n\n\n<li><strong>Simplified formula.<\/strong> <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-bebaec161b03879b767a124e83f1a745_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;&#58;&#72;&#32;&#61;&#32;&#40;&#65;&#94;&#123;&#45;&#49;&#125;&#43;&#72;&#94;&#123;&#45;&#49;&#125;&#41;&#94;&#123;&#45;&#49;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"20\" width=\"187\" style=\"vertical-align: -5px;\"\/> for positive definite matrices,<\/li>\n\n\n\n<li><strong>Bounds.<\/strong> <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-91e407caebda4c0b21900143b00ab41c_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;&#58;&#72;&#32;&#92;&#112;&#114;&#101;&#99;&#101;&#113;&#32;&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"81\" style=\"vertical-align: -3px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-eb93eb9292161a4fae89d9b44fac9cc6_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;&#58;&#72;&#32;&#92;&#112;&#114;&#101;&#99;&#101;&#113;&#32;&#72;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"84\" style=\"vertical-align: -3px;\"\/>.<\/li>\n\n\n\n<li><strong>Monotone.<\/strong> <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-0decad960e77b4caed97d3e30fac20f1_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;&#92;&#109;&#97;&#112;&#115;&#116;&#111;&#32;&#40;&#65;&#58;&#72;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"98\" style=\"vertical-align: -5px;\"\/> is <a href=\"https:\/\/en.wikipedia.org\/wiki\/Operator_monotone_function\">monotone<\/a> in the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Loewner_order\">Loewner order<\/a>.<\/li>\n\n\n\n<li><strong>Concavity.<\/strong> The map <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-ad63064bd7322d8ca8b66a2adb7e4b7b_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#40;&#65;&#44;&#72;&#41;&#32;&#92;&#109;&#97;&#112;&#115;&#116;&#111;&#32;&#65;&#58;&#72;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"122\" style=\"vertical-align: -5px;\"\/> is <a href=\"https:\/\/www.google.com\/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=&amp;ved=2ahUKEwiZjMOKpcH_AhUVLUQIHa_2AMwQFnoECAgQAQ&amp;url=https%3A%2F%2Flink.springer.com%2Fcontent%2Fpdf%2F10.1007%2F978-1-4612-0653-8_5.pdf&amp;usg=AOvVaw3wVvkkFGh3wX9Nm75kPtkL\">(jointly) concave<\/a> (with respect to the Loewner order).<\/li>\n\n\n\n<li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Matrix_congruence\"><strong>Conjugation.<\/strong><\/a> For any square <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-52134c3741ef3371f17ceb962d0792f6_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#67;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/>, <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-d0d97d64fd79c9b08b72bcacbba88fd4_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#67;&#94;&#42;&#40;&#65;&#58;&#72;&#41;&#67;&#32;&#61;&#32;&#40;&#67;&#94;&#42;&#65;&#67;&#41;&#58;&#40;&#67;&#94;&#42;&#72;&#67;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"259\" style=\"vertical-align: -5px;\"\/>.<\/li>\n\n\n\n<li><strong>Trace.<\/strong> <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-e5e01dd7d3bfab6766dfd918f46aefc3_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#116;&#114;&#40;&#65;&#58;&#72;&#41;&#32;&#92;&#108;&#101;&#32;&#40;&#92;&#116;&#114;&#32;&#65;&#41;&#58;&#40;&#92;&#116;&#114;&#32;&#72;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"200\" style=\"vertical-align: -5px;\"\/>.<\/li>\n<\/ol>\n\n\n\n<p>For completionists, we include a proof of the last property for reference.<\/p>\n\n\n\n<div class=\"su-spoiler su-spoiler-style-default su-spoiler-icon-plus su-spoiler-closed\" data-scroll-offset=\"0\" data-anchor-in-url=\"no\"><div class=\"su-spoiler-title\" tabindex=\"0\" role=\"button\"><span class=\"su-spoiler-icon\"><\/span>Proof of Property 8<\/div><div class=\"su-spoiler-content su-u-clearfix su-u-trim\">Let <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-a3412acdbdd8cccfc655f5740c96b872_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#99;&#100;&#111;&#116;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;&#39;\" title=\"Rendered by QuickLaTeX.com\" height=\"21\" width=\"36\" style=\"vertical-align: -5px;\"\/> be the unitarily invariant norm <a href=\"https:\/\/en.wikipedia.org\/wiki\/Dual_norm\"><em>dual<\/em><\/a> to <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-abf50ae9bad3b75e024229c18701f68b_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#99;&#100;&#111;&#116;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"36\" style=\"vertical-align: -5px;\"\/>.<sup class=\"modern-footnotes-footnote \" data-mfn=\"2\" data-mfn-post-scope=\"000000000000057f0000000000000000_1529\"><a href=\"javascript:void(0)\"  role=\"button\" aria-pressed=\"false\" aria-describedby=\"mfn-content-000000000000057f0000000000000000_1529-2\">2<\/a><\/sup><span id=\"mfn-content-000000000000057f0000000000000000_1529-2\" role=\"tooltip\" class=\"modern-footnotes-footnote__note\" tabindex=\"0\" data-mfn=\"2\">Dual with respect to the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Frobenius_inner_product\">Frobenius inner product<\/a>, that is.<\/span> By duality, we have<br><br><p class=\"ql-center-displayed-equation\" style=\"line-height: 254px;\"><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-4d5c2226a0ddf81d346da401ff4b53b9_l3.png\" height=\"254\" width=\"603\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#98;&#101;&#103;&#105;&#110;&#123;&#97;&#108;&#105;&#103;&#110;&#42;&#125;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#65;&#58;&#72;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;&#32;&#38;&#61;&#32;&#92;&#109;&#97;&#120;&#95;&#123;&#77;&#92;&#115;&#117;&#99;&#99;&#101;&#113;&#32;&#48;&#44;&#92;&#58;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#77;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;&#39;&#92;&#108;&#101;&#32;&#49;&#125;&#32;&#92;&#116;&#114;&#40;&#40;&#65;&#58;&#72;&#41;&#77;&#41;&#32;&#92;&#92;&#38;&#61;&#32;&#92;&#109;&#97;&#120;&#95;&#123;&#77;&#92;&#115;&#117;&#99;&#99;&#101;&#113;&#32;&#48;&#44;&#92;&#58;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#77;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;&#39;&#92;&#108;&#101;&#32;&#49;&#125;&#32;&#92;&#116;&#114;&#40;&#77;&#94;&#123;&#49;&#47;&#50;&#125;&#40;&#65;&#58;&#72;&#41;&#77;&#94;&#123;&#49;&#47;&#50;&#125;&#41;&#92;&#92;&#38;&#61;&#32;&#92;&#109;&#97;&#120;&#95;&#123;&#77;&#92;&#115;&#117;&#99;&#99;&#101;&#113;&#32;&#48;&#44;&#92;&#58;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#77;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;&#39;&#92;&#108;&#101;&#32;&#49;&#125;&#32;&#92;&#116;&#114;&#40;&#40;&#77;&#94;&#123;&#49;&#47;&#50;&#125;&#65;&#77;&#94;&#123;&#49;&#47;&#50;&#125;&#41;&#58;&#40;&#77;&#94;&#123;&#49;&#47;&#50;&#125;&#72;&#77;&#94;&#123;&#49;&#47;&#50;&#125;&#41;&#41;&#32;&#32;&#92;&#92;&#38;&#92;&#108;&#101;&#32;&#92;&#109;&#97;&#120;&#95;&#123;&#77;&#92;&#115;&#117;&#99;&#99;&#101;&#113;&#32;&#48;&#44;&#92;&#58;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#77;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;&#39;&#92;&#108;&#101;&#32;&#49;&#125;&#32;&#92;&#108;&#101;&#102;&#116;&#091;&#92;&#116;&#114;&#40;&#77;&#94;&#123;&#49;&#47;&#50;&#125;&#65;&#77;&#94;&#123;&#49;&#47;&#50;&#125;&#41;&#58;&#92;&#116;&#114;&#40;&#77;&#94;&#123;&#49;&#47;&#50;&#125;&#72;&#77;&#94;&#123;&#49;&#47;&#50;&#125;&#41;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#093;&#32;&#92;&#92;&#38;&#92;&#108;&#101;&#32;&#92;&#108;&#101;&#102;&#116;&#091;&#92;&#109;&#97;&#120;&#95;&#123;&#77;&#92;&#115;&#117;&#99;&#99;&#101;&#113;&#32;&#48;&#44;&#92;&#58;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#77;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;&#39;&#92;&#108;&#101;&#32;&#49;&#125;&#32;&#92;&#116;&#114;&#40;&#77;&#94;&#123;&#49;&#47;&#50;&#125;&#65;&#77;&#94;&#123;&#49;&#47;&#50;&#125;&#41;&#92;&#114;&#105;&#103;&#104;&#116;&#093;&#58;&#92;&#108;&#101;&#102;&#116;&#091;&#92;&#109;&#97;&#120;&#95;&#123;&#77;&#92;&#115;&#117;&#99;&#99;&#101;&#113;&#32;&#48;&#44;&#92;&#58;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#77;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;&#39;&#92;&#108;&#101;&#32;&#49;&#125;&#32;&#92;&#116;&#114;&#40;&#77;&#94;&#123;&#49;&#47;&#50;&#125;&#72;&#77;&#94;&#123;&#49;&#47;&#50;&#125;&#41;&#92;&#114;&#105;&#103;&#104;&#116;&#093;&#92;&#92;&#38;&#61;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#65;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;&#32;&#58;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#72;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;&#46;&#92;&#101;&#110;&#100;&#123;&#97;&#108;&#105;&#103;&#110;&#42;&#125;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><br>The first line is duality, the second holds because <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-4b28d036a996c1bd1f3bdf05b8d84d73_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#77;&#92;&#115;&#117;&#99;&#99;&#101;&#113;&#32;&#48;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"52\" style=\"vertical-align: -3px;\"\/>, the third line is property 6, the fourth line is property 7, the fifth line is property 4, and the sixth line is duality.<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\">Nearing the Finish: Enter the Randomness<\/h2>\n\n\n\n<p>Equipped with knowledge about parallel sums, we are now prepared to return to bounding the error of the randomized SVD. Apply property 8 of the parallel sum to the randomized SVD bound (7) to obtain<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 118px;\"><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-df07b0b9660af51129fd29552ad6c650_l3.png\" height=\"118\" width=\"448\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#98;&#101;&#103;&#105;&#110;&#123;&#97;&#108;&#105;&#103;&#110;&#42;&#125;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#66;&#32;&#45;&#32;&#88;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#94;&#50;&#38;&#92;&#108;&#101;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#32;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#94;&#50;&#32;&#43;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#94;&#50;&#32;&#58;&#32;&#091;&#40;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#41;&#94;&#42;&#40;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#41;&#093;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;&#32;&#92;&#92;&#38;&#92;&#108;&#101;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#32;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#94;&#50;&#32;&#43;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#94;&#50;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;&#32;&#58;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#091;&#40;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#41;&#94;&#42;&#40;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#41;&#093;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#85;&#73;&#125;&#32;&#92;&#92;&#38;&#61;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#32;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#94;&#50;&#32;&#43;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#49;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#94;&#50;&#32;&#58;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#94;&#50;&#95;&#123;&#92;&#114;&#109;&#32;&#81;&#125;&#46;&#92;&#101;&#110;&#100;&#123;&#97;&#108;&#105;&#103;&#110;&#42;&#125;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>This bound is totally deterministic: It holds for any choice of test matrix <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-0e42a68047144196ffa9763b964056ac_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#79;&#109;&#101;&#103;&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"12\" style=\"vertical-align: 0px;\"\/>, random or otherwise. We can use this bound to analyze the randomized SVD in many different ways for different kinds of random (or non-random) matrices <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-0e42a68047144196ffa9763b964056ac_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#79;&#109;&#101;&#103;&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"12\" style=\"vertical-align: 0px;\"\/>. Tropp and Webber provide a number of examples instantiating this general bound in different ways.<\/p>\n\n\n\n<p>We shall present only the simplest error bound for randomized SVD. We make the following assumptions:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The test matrix <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-0e42a68047144196ffa9763b964056ac_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#79;&#109;&#101;&#103;&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"12\" style=\"vertical-align: 0px;\"\/> is standard Gaussian.<\/li>\n<\/ul>\n\n\n\n<p>Under these assumptions and using the property <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-bd9b2d197f119bc6d01152293baa39e4_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#97;&#32;&#58;&#32;&#104;&#32;&#92;&#108;&#101;&#32;&#104;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"68\" style=\"vertical-align: -3px;\"\/>, we obtain the following expression for the expected error of the randomized SVD<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 36px;\"><span class=\"ql-right-eqno\"> (9) <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-3f9645663663b82d968efe393fc4c158_l3.png\" height=\"36\" width=\"352\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#69;&#125;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#66;&#32;&#45;&#32;&#88;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#92;&#108;&#101;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#32;&#66;&#32;&#45;&#32;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#114;&#32;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#32;&#43;&#32;&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#69;&#125;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#94;&#50;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#46;&#32;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>All that is left to is compute the expectation of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-c6309dede4d77ac87c6c5196445d91b4_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;\" title=\"Rendered by QuickLaTeX.com\" height=\"36\" width=\"88\" style=\"vertical-align: -12px;\"\/>. Remarkably, this can be done in closed form.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Aside: Expectation of Gaussian\u2013Inverse Gaussian Matrix Product<\/h2>\n\n\n\n<p>The final ingredient in our randomized SVD analysis is the following computation involving Gaussian random matrices. Let <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-53c2a72f422a8e6f02f2e3ac92c66d78_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#71;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-d7c5deff4fd921979ee0de5147b33a04_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#71;&#97;&#109;&#109;&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"11\" style=\"vertical-align: 0px;\"\/> be independent standard Gaussian random matrices with <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-d7c5deff4fd921979ee0de5147b33a04_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#71;&#97;&#109;&#109;&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"11\" style=\"vertical-align: 0px;\"\/> of size <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-a0b68aca8ae574ae9287ad492289d67c_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#114;&#92;&#116;&#105;&#109;&#101;&#115;&#32;&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"39\" style=\"vertical-align: 0px;\"\/>, <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-d745ab727b3cb38d260d608c88f15710_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;&#92;&#103;&#101;&#32;&#114;&#45;&#50;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"72\" style=\"vertical-align: -3px;\"\/>. Then<\/p>\n\n\n\n<p><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-83f5771c01f2d031fd755830d363cda0_l3.png\" height=\"41\" width=\"307\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#69;&#125;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#83;&#71;&#92;&#71;&#97;&#109;&#109;&#97;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#82;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#32;&#61;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#49;&#125;&#123;&#107;&#45;&#40;&#114;&#43;&#49;&#41;&#125;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#83;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#82;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>For the probability lovers, we will now go on to prove this. For those who are less probabilistically inclined, this result can be treated as a black box.<\/p>\n\n\n\n<div class=\"su-spoiler su-spoiler-style-default su-spoiler-icon-plus su-spoiler-closed\" data-scroll-offset=\"0\" data-anchor-in-url=\"no\"><div class=\"su-spoiler-title\" tabindex=\"0\" role=\"button\"><span class=\"su-spoiler-icon\"><\/span>Proof of Random Matrix Formula<\/div><div class=\"su-spoiler-content su-u-clearfix su-u-trim\">To prove this, first consider a simpler case where <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-36c5960433360ce72c9ed735c5121451_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#71;&#97;&#109;&#109;&#97;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"17\" style=\"vertical-align: 0px;\"\/> does not appear:<br><br><p class=\"ql-center-displayed-equation\" style=\"line-height: 60px;\"><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-dc219fd0dab2748965ecbf439c051db5_l3.png\" height=\"60\" width=\"521\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#69;&#125;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#83;&#71;&#87;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#32;&#61;&#32;&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#69;&#125;&#32;&#92;&#115;&#117;&#109;&#95;&#123;&#105;&#106;&#125;&#32;&#92;&#108;&#101;&#102;&#116;&#40;&#92;&#115;&#117;&#109;&#95;&#123;&#107;&#92;&#101;&#108;&#108;&#125;&#32;&#115;&#95;&#123;&#105;&#107;&#125;&#103;&#95;&#123;&#107;&#92;&#101;&#108;&#108;&#125;&#119;&#95;&#123;&#92;&#101;&#108;&#108;&#32;&#106;&#125;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#41;&#94;&#50;&#32;&#61;&#32;&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#69;&#125;&#32;&#92;&#115;&#117;&#109;&#95;&#123;&#105;&#106;&#107;&#92;&#101;&#108;&#108;&#125;&#32;&#115;&#95;&#123;&#105;&#107;&#125;&#94;&#50;&#32;&#119;&#95;&#123;&#92;&#101;&#108;&#108;&#32;&#106;&#125;&#94;&#50;&#32;&#61;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#83;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#87;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><br><br>Here, we used the fact that the entries <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-0cda607689e37f21af2dfc4cd3b594f9_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#103;&#95;&#123;&#107;&#92;&#101;&#108;&#108;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"22\" style=\"vertical-align: -4px;\"\/> are independent, mean-zero, and variance-one. Thus, applying this result conditionally on <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-d7c5deff4fd921979ee0de5147b33a04_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#71;&#97;&#109;&#109;&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"11\" style=\"vertical-align: 0px;\"\/> with <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-1b09553fbe8418aaa7bc1344213386e5_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#87;&#32;&#61;&#32;&#92;&#71;&#97;&#109;&#109;&#97;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#82;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"75\" style=\"vertical-align: 0px;\"\/>, we get<br><br><p class=\"ql-center-displayed-equation\" style=\"line-height: 44px;\"><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-31c52f341c1e50d4e2c2e8583f3a7737_l3.png\" height=\"44\" width=\"461\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#69;&#125;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#83;&#71;&#92;&#71;&#97;&#109;&#109;&#97;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#82;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#32;&#61;&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#69;&#125;&#92;&#108;&#101;&#102;&#116;&#091;&#32;&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#69;&#125;&#92;&#108;&#101;&#102;&#116;&#091;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#83;&#71;&#92;&#71;&#97;&#109;&#109;&#97;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#82;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#32;&#92;&#44;&#92;&#109;&#105;&#100;&#100;&#108;&#101;&#124;&#92;&#44;&#32;&#92;&#71;&#97;&#109;&#109;&#97;&#92;&#114;&#105;&#103;&#104;&#116;&#093;&#92;&#114;&#105;&#103;&#104;&#116;&#093;&#32;&#61;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#83;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#92;&#99;&#100;&#111;&#116;&#32;&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#69;&#125;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#71;&#97;&#109;&#109;&#97;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#82;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#46;&#32;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><br><br>To compute <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-9d93e45cab4ca13c2f7a511fe424bb2d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#69;&#125;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#71;&#97;&#109;&#109;&#97;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#82;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;\" title=\"Rendered by QuickLaTeX.com\" height=\"26\" width=\"75\" style=\"vertical-align: -7px;\"\/>, we rewrite using the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Trace_(linear_algebra)\">trace<\/a><br><br><p class=\"ql-center-displayed-equation\" style=\"line-height: 37px;\"><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-79bd47bd70f2015a46c038c4f0d0e5f7_l3.png\" height=\"37\" width=\"573\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#69;&#125;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#71;&#97;&#109;&#109;&#97;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#82;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#32;&#61;&#32;&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#69;&#125;&#32;&#92;&#116;&#114;&#32;&#92;&#108;&#101;&#102;&#116;&#40;&#92;&#71;&#97;&#109;&#109;&#97;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#82;&#82;&#94;&#42;&#32;&#92;&#71;&#97;&#109;&#109;&#97;&#94;&#123;&#42;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#125;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#41;&#61;&#32;&#92;&#116;&#114;&#32;&#92;&#108;&#101;&#102;&#116;&#40;&#82;&#82;&#94;&#42;&#32;&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#69;&#125;&#091;&#92;&#71;&#97;&#109;&#109;&#97;&#94;&#123;&#42;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#125;&#92;&#71;&#97;&#109;&#109;&#97;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#093;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#41;&#32;&#61;&#32;&#92;&#116;&#114;&#32;&#92;&#108;&#101;&#102;&#116;&#40;&#82;&#82;&#94;&#42;&#32;&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#69;&#125;&#091;&#40;&#92;&#71;&#97;&#109;&#109;&#97;&#92;&#71;&#97;&#109;&#109;&#97;&#94;&#42;&#41;&#94;&#123;&#45;&#49;&#125;&#093;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#41;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><br><br>The matrix <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-fb4ef72a96df9cc03ce0399154bdaaef_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#40;&#92;&#71;&#97;&#109;&#109;&#97;&#92;&#71;&#97;&#109;&#109;&#97;&#94;&#42;&#41;&#94;&#123;&#45;&#49;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"20\" width=\"60\" style=\"vertical-align: -5px;\"\/> is known as an <a href=\"https:\/\/en.wikipedia.org\/wiki\/Inverse-Wishart_distribution\">inverse-Wishart matrix<\/a> and is a well-studied random matrix model. In particular, its expectation is known to be <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-676eee0e8a8325e27cd958a8a0b70cb2_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#40;&#107;&#45;&#40;&#114;&#43;&#49;&#41;&#41;&#94;&#123;&#45;&#49;&#125;&#73;\" title=\"Rendered by QuickLaTeX.com\" height=\"20\" width=\"124\" style=\"vertical-align: -5px;\"\/>. Thus, we obtain<br><br><p class=\"ql-center-displayed-equation\" style=\"line-height: 47px;\"><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-e874bd74b5ef81c13856de05454ea647_l3.png\" height=\"47\" width=\"479\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#69;&#125;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#71;&#97;&#109;&#109;&#97;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#82;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#32;&#61;&#32;&#92;&#116;&#114;&#32;&#92;&#108;&#101;&#102;&#116;&#40;&#82;&#82;&#94;&#42;&#32;&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#69;&#125;&#091;&#40;&#92;&#71;&#97;&#109;&#109;&#97;&#92;&#71;&#97;&#109;&#109;&#97;&#94;&#42;&#41;&#94;&#123;&#45;&#49;&#125;&#093;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#41;&#32;&#61;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#92;&#116;&#114;&#32;&#92;&#108;&#101;&#102;&#116;&#40;&#82;&#82;&#94;&#42;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#41;&#125;&#123;&#107;&#45;&#40;&#114;&#43;&#49;&#41;&#125;&#32;&#61;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#82;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#125;&#123;&#107;&#45;&#40;&#114;&#43;&#49;&#41;&#125;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><br><br>Plugging into (10), we obtain the desired conclusion<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 42px;\"><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-b2ac63d48bafba095409bc148beed39c_l3.png\" height=\"42\" width=\"459\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#69;&#125;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#83;&#71;&#92;&#71;&#97;&#109;&#109;&#97;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#82;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#32;&#61;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#83;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#92;&#99;&#100;&#111;&#116;&#32;&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#69;&#125;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#71;&#97;&#109;&#109;&#97;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#82;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#32;&#61;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#49;&#125;&#123;&#107;&#45;&#40;&#114;&#43;&#49;&#41;&#125;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#83;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#82;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><br><br>This completes the proof.<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\">Wrapping it All Up<\/h2>\n\n\n\n<p>We&#8217;re now within striking distance. All that is left is to assemble the pieces we have been working with to obtain a final bound for the randomized SVD.<\/p>\n\n\n\n<p>Recall we have chosen the random matrix <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-0e42a68047144196ffa9763b964056ac_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#79;&#109;&#101;&#103;&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"12\" style=\"vertical-align: 0px;\"\/> to be standard Gaussian. By the rotational invariance of the Gaussian distribution, <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-8054fed550f38ce14b26d47a239efccc_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"19\" style=\"vertical-align: -3px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-9e97bbfc79fca9fb49929f4707c5b74c_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#50;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"20\" style=\"vertical-align: -3px;\"\/> are independent and standard Gaussian as well. Plugging the matrix expectation bound to (9) then completes the analysis<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 138px;\"><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-7297d914330df89c8f00d9bd45e9a3f3_l3.png\" height=\"138\" width=\"379\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#98;&#101;&#103;&#105;&#110;&#123;&#97;&#108;&#105;&#103;&#110;&#42;&#125;&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#69;&#125;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#66;&#32;&#45;&#32;&#88;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#38;&#92;&#108;&#101;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#32;&#66;&#32;&#45;&#32;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#114;&#32;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#32;&#43;&#32;&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#69;&#125;&#92;&#110;&#111;&#114;&#109;&#123;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#50;&#92;&#79;&#109;&#101;&#103;&#97;&#95;&#49;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#73;&#95;&#123;&#107;&#92;&#116;&#105;&#109;&#101;&#115;&#32;&#107;&#125;&#125;&#94;&#50;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#32;&#92;&#92;&#38;&#61;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#32;&#66;&#32;&#45;&#32;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#114;&#32;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#32;&#43;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#92;&#83;&#105;&#103;&#109;&#97;&#95;&#50;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#92;&#110;&#111;&#114;&#109;&#123;&#73;&#95;&#123;&#107;&#92;&#116;&#105;&#109;&#101;&#115;&#32;&#107;&#125;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#125;&#123;&#107;&#45;&#40;&#114;&#43;&#49;&#41;&#125;&#32;&#92;&#92;&#38;&#61;&#32;&#92;&#108;&#101;&#102;&#116;&#40;&#49;&#32;&#43;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#107;&#125;&#123;&#107;&#45;&#40;&#114;&#43;&#49;&#41;&#125;&#92;&#114;&#105;&#103;&#104;&#116;&#41;&#32;&#92;&#108;&#101;&#102;&#116;&#92;&#124;&#32;&#66;&#32;&#45;&#32;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#92;&#114;&#105;&#103;&#104;&#116;&#92;&#124;&#95;&#114;&#32;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#46;&#92;&#101;&#110;&#100;&#123;&#97;&#108;&#105;&#103;&#110;&#42;&#125;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>In the previous post, we looked at the randomized SVD. In this post, we continue this discussion by looking at the analysis of the randomized SVD. Our approach is adapted from a new analysis of the randomized SVD by Joel A. Tropp and Robert J. Webber. There are many types of analysis one can do<a class=\"more-link\" href=\"https:\/\/www.ethanepperly.com\/index.php\/2023\/06\/22\/low-rank-approximation-toolbox-analysis-of-the-randomized-svd\/\">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":[8],"tags":[],"class_list":["post-1529","post","type-post","status-publish","format-standard","hentry","category-low-rank-approximation-toolbox"],"_links":{"self":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts\/1529","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=1529"}],"version-history":[{"count":27,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts\/1529\/revisions"}],"predecessor-version":[{"id":2084,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts\/1529\/revisions\/2084"}],"wp:attachment":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/media?parent=1529"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/categories?post=1529"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/tags?post=1529"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}