{"id":2247,"date":"2026-05-20T13:19:40","date_gmt":"2026-05-20T13:19:40","guid":{"rendered":"https:\/\/www.ethanepperly.com\/?p=2247"},"modified":"2026-05-20T20:15:12","modified_gmt":"2026-05-20T20:15:12","slug":"low-rank-approximation-toolbox-generalized-nystrom-approximation","status":"publish","type":"post","link":"https:\/\/www.ethanepperly.com\/index.php\/2026\/05\/20\/low-rank-approximation-toolbox-generalized-nystrom-approximation\/","title":{"rendered":"Low-Rank Approximation Toolbox: Generalized Nystr\u00f6m Approximation"},"content":{"rendered":"\n<p>Today, I want to talk about the generalized Nystr\u00f6m approximation, which I regard as the one of the &#8220;big three&#8221; approaches to constructing a low-rank approximation to matrix.<sup class=\"modern-footnotes-footnote \" data-mfn=\"1\" data-mfn-post-scope=\"00000000000005840000000000000000_2247\"><a href=\"javascript:void(0)\"  role=\"button\" aria-pressed=\"false\" aria-describedby=\"mfn-content-00000000000005840000000000000000_2247-1\">1<\/a><\/sup><span id=\"mfn-content-00000000000005840000000000000000_2247-1\" role=\"tooltip\" class=\"modern-footnotes-footnote__note\" tabindex=\"0\" data-mfn=\"1\">The other two approaches are the &#8220;projection approximation&#8221;\/<a href=\"https:\/\/www.ethanepperly.com\/index.php\/2023\/06\/12\/low-rank-approximation-toolbox-randomized-svd\/\">randomized SVD<\/a> approach and the <a href=\"https:\/\/www.ethanepperly.com\/index.php\/2022\/10\/11\/low-rank-approximation-toolbox-nystrom-approximation\/\">Nystr\u00f6m approximation<\/a>.<\/span> Understanding this approximation, under what conditions it works and the sharpest possible error bounds for it, is a subject of two recent papers of mine:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><em><a href=\"https:\/\/arxiv.org\/abs\/2508.21189\">Faster Randomized Linear Algebra with Structured Random Matrices<\/a><\/em>, joint with <a href=\"https:\/\/chriscamano.github.io\">Chris Cama\u00f1o<\/a>, <a href=\"https:\/\/ram900.com\">Raphael Meyer<\/a>, and <a href=\"https:\/\/tropp.caltech.edu\">Joel Tropp<\/a>. <\/li>\n\n\n\n<li><em><a href=\"https:\/\/arxiv.org\/abs\/2605.19096\">Sharp analysis of sketched least squares and randomized low-rank approximation<\/a><\/em>, joint with <a href=\"https:\/\/sites.google.com\/ucsd.edu\/rwebber\/\">Robert Webber<\/a>.<\/li>\n<\/ul>\n\n\n\n<p>On the occasion of the release of the second paper this morning, I felt it was a good time to talk about the generalized Nystr\u00f6m approximation on this blog. In this post, I will try and motivate the generalized Nystr\u00f6m approximation, describing the motivation for the method and when it might be preferable to alternatives.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Existing Characters: <a href=\"https:\/\/www.ethanepperly.com\/index.php\/2022\/10\/11\/low-rank-approximation-toolbox-nystrom-approximation\/\">Nystr\u00f6m Approximation<\/a> and the <a href=\"https:\/\/www.ethanepperly.com\/index.php\/2023\/06\/12\/low-rank-approximation-toolbox-randomized-svd\/\">Randomized SVD<\/a><\/h2>\n\n\n\n<p>To begin our story, let me begin with a reminder of a couple of characters we&#8217;ve met in <a href=\"https:\/\/www.ethanepperly.com\/index.php\/category\/low-rank-approximation-toolbox\/\">previous installments<\/a> of this blog, <a href=\"https:\/\/www.ethanepperly.com\/index.php\/2022\/10\/11\/low-rank-approximation-toolbox-nystrom-approximation\/\">randomized Nystr\u00f6m approximation<\/a> and the <a href=\"https:\/\/www.ethanepperly.com\/index.php\/2023\/06\/12\/low-rank-approximation-toolbox-randomized-svd\/\">randomized SVD<\/a>.<\/p>\n\n\n\n<p>Randomized Nystr\u00f6m approximation is a method for producing a low-rank approximation to a <em><a href=\"https:\/\/en.wikipedia.org\/wiki\/Definite_matrix#Definitions\">positive semidefinite<\/a><\/em><sup class=\"modern-footnotes-footnote \" data-mfn=\"2\" data-mfn-post-scope=\"00000000000005840000000000000000_2247\"><a href=\"javascript:void(0)\"  role=\"button\" aria-pressed=\"false\" aria-describedby=\"mfn-content-00000000000005840000000000000000_2247-2\">2<\/a><\/sup><span id=\"mfn-content-00000000000005840000000000000000_2247-2\" role=\"tooltip\" class=\"modern-footnotes-footnote__note\" tabindex=\"0\" data-mfn=\"2\">For this post, a positive semidefinite matrix will always be real <a href=\"https:\/\/en.wikipedia.org\/wiki\/Symmetric_matrix\">symmetric<\/a> or complex <a href=\"https:\/\/en.wikipedia.org\/wiki\/Hermitian_matrix\">Hermitian<\/a>. We will focus only on real matrices for this post, though the extension to complex matrices is straightforward.<\/span> (psd) matrix <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-11f4f587954b361e7d78940f65b8d70d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"13\" style=\"vertical-align: 0px;\"\/>. For form this approximation, begin by drawing a random 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;\"\/>, say, with <a href=\"https:\/\/en.wikipedia.org\/wiki\/Independence_(probability_theory)\">independent<\/a> <a href=\"https:\/\/en.wikipedia.org\/wiki\/Normal_distribution#Definitions\">standard normal<\/a> random entries. (We will have more to say about the choice of <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;\"\/> below). Using this test matrix, the Nystr\u00f6m approximation is defined as<sup class=\"modern-footnotes-footnote \" data-mfn=\"3\" data-mfn-post-scope=\"00000000000005840000000000000000_2247\"><a href=\"javascript:void(0)\"  role=\"button\" aria-pressed=\"false\" aria-describedby=\"mfn-content-00000000000005840000000000000000_2247-3\">3<\/a><\/sup><span id=\"mfn-content-00000000000005840000000000000000_2247-3\" role=\"tooltip\" class=\"modern-footnotes-footnote__note\" tabindex=\"0\" data-mfn=\"3\">Here, the inverse <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-1afab552eac419fae92a537c269157d8_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#123;&#125;&#94;&#123;&#45;&#49;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"9\" width=\"16\" style=\"vertical-align: 6px;\"\/> should be interpreted as a <a href=\"https:\/\/en.wikipedia.org\/wiki\/Moore\u2013Penrose_inverse\">Moore\u2013Penrose pseudoinverse<\/a> in the event where <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-5d0ef7d123813c3364936c07e13f161a_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#79;&#109;&#101;&#103;&#97;&#94;&#92;&#116;&#111;&#112;&#32;&#65;&#32;&#92;&#79;&#109;&#101;&#103;&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"49\" style=\"vertical-align: 0px;\"\/> is <a href=\"https:\/\/en.wikipedia.org\/wiki\/Singular_matrix\">singular<\/a>.<\/span> <p class=\"ql-center-displayed-equation\" style=\"line-height: 24px;\"><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-858ee4e7300bc0e48d12677bd459aeaf_l3.png\" height=\"24\" width=\"201\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#104;&#97;&#116;&#123;&#65;&#125;&#32;&#61;&#32;&#65;&#92;&#79;&#109;&#101;&#103;&#97;&#32;&#40;&#92;&#79;&#109;&#101;&#103;&#97;&#94;&#92;&#116;&#111;&#112;&#32;&#65;&#92;&#79;&#109;&#101;&#103;&#97;&#41;&#94;&#123;&#45;&#49;&#125;&#32;&#40;&#65;&#92;&#79;&#109;&#101;&#103;&#97;&#41;&#94;&#92;&#116;&#111;&#112;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>To implement this algorithm in practice, one should take care to use numerically stable pseudocode; see <a href=\"https:\/\/arxiv.org\/abs\/1706.05736\">this paper<\/a> for details.<\/p>\n\n\n\n<p>The <a href=\"https:\/\/www.ethanepperly.com\/index.php\/2023\/06\/12\/low-rank-approximation-toolbox-randomized-svd\/\">randomized SVD<\/a> is a method for constructing a low-rank approximation to a general, non-symmetric or even non-square matrix <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;\"\/>. Again, begin by constructing a random 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;\"\/>. To construct a low-rank approximation, compute the product <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;\"\/> and <a href=\"[https:\/\/en.wikipedia.org\/wiki\/QR_decomposition](https:\/\/en.wikipedia.org\/wiki\/Orthonormality)\">orthonormalize<\/a> its columns (e.g., by <a href=\"https:\/\/en.wikipedia.org\/wiki\/QR_decomposition\">QR decomposition<\/a>) to obtain <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-77d0237ae3f34369630eff1996a39563_l3.png\" height=\"19\" width=\"119\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#81;&#32;&#92;&#99;&#111;&#108;&#111;&#110;&#101;&#113;&#113;&#32;&#92;&#111;&#112;&#101;&#114;&#97;&#116;&#111;&#114;&#110;&#97;&#109;&#101;&#123;&#111;&#114;&#116;&#104;&#125;&#40;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#41;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>Then, to construct a low-rank approximation, we employ a second product with the matrix <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;\"\/>, yielding the low-rank approximation <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-f9906f14f437fa982d3c8a2311d36ee3_l3.png\" height=\"23\" width=\"192\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#104;&#97;&#116;&#123;&#66;&#125;&#32;&#61;&#32;&#81;&#67;&#32;&#92;&#113;&#117;&#97;&#100;&#32;&#92;&#116;&#101;&#120;&#116;&#123;&#102;&#111;&#114;&#32;&#125;&#32;&#67;&#32;&#61;&#32;&#81;&#94;&#92;&#116;&#111;&#112;&#32;&#66;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>How do these two algorithms compare? There are at least three major differences between the two algorithms. Here are the first two:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Scope.<\/strong> Nystr\u00f6m approximation applies only to psd matrices, and randomized SVD applies to a general rectangular mtrix.<\/li>\n\n\n\n<li><strong>Single-pass?<\/strong> The Nystr\u00f6m approximation requires only a single pass over the matrix <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-11f4f587954b361e7d78940f65b8d70d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"13\" style=\"vertical-align: 0px;\"\/> to form. (Each entry of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-11f4f587954b361e7d78940f65b8d70d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"13\" style=\"vertical-align: 0px;\"\/> needs to be read once to form the product <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-c04f253ed18b3f436fd8d1f4c520cfcf_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;&#92;&#79;&#109;&#101;&#103;&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"25\" style=\"vertical-align: 0px;\"\/>, after which we have all the information we need from <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-11f4f587954b361e7d78940f65b8d70d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"13\" style=\"vertical-align: 0px;\"\/> to form <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-a9463bba1bf140207248e89a02db1929_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#104;&#97;&#116;&#123;&#65;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"18\" width=\"14\" style=\"vertical-align: 0px;\"\/>.) By contrast, the randomized SVD requires two passes, one to compute <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;\"\/> and a second to compute <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-8dba5ca0d8880af6cb4b15cfdf65d0d6_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#81;&#94;&#92;&#116;&#111;&#112;&#32;&#66;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"40\" style=\"vertical-align: -4px;\"\/>.<\/li>\n<\/ol>\n\n\n\n<p>The third point is more subtle and concerns the <em>accuracy<\/em> of these algorithms. As we saw in <a href=\"https:\/\/www.ethanepperly.com\/index.php\/2023\/06\/22\/low-rank-approximation-toolbox-analysis-of-the-randomized-svd\/\">a previous post<\/a>, the randomized SVD approximation satisfies the error bound <p class=\"ql-center-displayed-equation\" style=\"line-height: 43px;\"><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-e3bfd87c8b50495a7a32c42f0af681ac_l3.png\" height=\"43\" width=\"418\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#101;&#120;&#112;&#101;&#99;&#116;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#66;&#32;&#45;&#32;&#92;&#104;&#97;&#116;&#123;&#66;&#125;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#32;&#92;&#108;&#101;&#32;&#92;&#109;&#105;&#110;&#95;&#123;&#114;&#32;&#92;&#108;&#101;&#32;&#107;&#45;&#50;&#125;&#32;&#92;&#108;&#101;&#102;&#116;&#40;&#32;&#49;&#32;&#43;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#114;&#125;&#123;&#107;&#45;&#40;&#114;&#43;&#49;&#41;&#125;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#41;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#66;&#32;&#45;&#32;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#46;&#32;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>Here, <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-a1c68b4e06aabf59a565a9f21fa9242d_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;&#70;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"30\" style=\"vertical-align: -5px;\"\/> is the matrix <a href=\"https:\/\/en.wikipedia.org\/wiki\/Matrix_norm#Frobenius_norm\">Frobenius norm<\/a> and <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;\"\/> denotes the <a href=\"%3Chttps:\/\/en.wikipedia.org\/wiki\/Low-rank_approximation#Proof_of_Eckart\u2013Young\u2013Mirsky_theorem_(for_Frobenius_norm)%3E\">best<\/a> 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;\"\/>. This result, due to <a href=\"https:\/\/arxiv.org\/abs\/0909.4061\">Halko, Martinsson, &amp; Tropp (2011)<\/a>, shows that the error of 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;\"\/> randomized SVD is comparable to the error of the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Low-rank_approximation#Proof_of_Eckart\u2013Young\u2013Mirsky_theorem_(for_Frobenius_norm)\">best<\/a> 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;\"\/> of any rank <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-ee146d1aba4b54d01319e2838916b608_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#114;&#92;&#108;&#101;&#32;&#107;&#45;&#50;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"72\" style=\"vertical-align: -3px;\"\/>. See <a href=\"https:\/\/www.ethanepperly.com\/index.php\/2023\/06\/22\/low-rank-approximation-toolbox-analysis-of-the-randomized-svd\/\">this post<\/a> for more discussion of this error bound.<\/p>\n\n\n\n<p>Here is analogous bound for the randomized Nystr\u00f6m approximation, taken from Corollary 8.3 in <a href=\"https:\/\/arxiv.org\/abs\/2306.12418v3\">this paper<\/a> of Tropp and Webber: <p class=\"ql-center-displayed-equation\" style=\"line-height: 48px;\"><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-af14e93166cedc601f5dee4cc4155a7a_l3.png\" height=\"48\" width=\"656\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#108;&#101;&#102;&#116;&#40;&#92;&#101;&#120;&#112;&#101;&#99;&#116;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#65;&#32;&#45;&#32;&#92;&#104;&#97;&#116;&#123;&#65;&#125;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#41;&#94;&#123;&#49;&#47;&#50;&#125;&#32;&#92;&#108;&#101;&#32;&#92;&#109;&#105;&#110;&#95;&#123;&#114;&#92;&#108;&#101;&#32;&#107;&#45;&#52;&#125;&#32;&#92;&#108;&#101;&#102;&#116;&#40;&#49;&#32;&#43;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#114;&#43;&#49;&#125;&#123;&#107;&#45;&#40;&#114;&#43;&#51;&#41;&#125;&#92;&#114;&#105;&#103;&#104;&#116;&#41;&#32;&#92;&#108;&#101;&#102;&#116;&#40;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#65;&#32;&#45;&#32;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#65;&#125;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#32;&#43;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#49;&#125;&#123;&#92;&#115;&#113;&#114;&#116;&#123;&#107;&#45;&#114;&#125;&#125;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#65;&#32;&#45;&#32;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#65;&#125;&#95;&#114;&#125;&#95;&#42;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#41;&#46;&#32;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>This bound is more complicated than the bound for the randomized SVD in several ways. For us, let us focus on one main difference: The error of the randomized Nystr\u00f6m approximation depends on the <em><a href=\"https:\/\/en.wikipedia.org\/wiki\/Schatten_norm#Special_cases\">nuclear norm<\/a><\/em> error <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-d686d2b71fd166eb3b16487d425438f6_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#110;&#111;&#114;&#109;&#123;&#65;&#32;&#45;&#32;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#65;&#125;&#95;&#114;&#125;&#95;&#42;\" title=\"Rendered by QuickLaTeX.com\" height=\"20\" width=\"92\" style=\"vertical-align: -6px;\"\/> of 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.<\/p>\n\n\n\n<p>The <a href=\"https:\/\/en.wikipedia.org\/wiki\/Schatten_norm#Special_cases\">nuclear norm<\/a> <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-70e4f079cb458b88416ee8f1c2f9ec2b_l3.png\" height=\"19\" width=\"215\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#110;&#111;&#114;&#109;&#123;&#67;&#125;&#95;&#42;&#32;&#61;&#32;&#92;&#115;&#105;&#103;&#109;&#97;&#95;&#49;&#40;&#67;&#41;&#32;&#43;&#32;&#92;&#115;&#105;&#103;&#109;&#97;&#95;&#50;&#40;&#67;&#41;&#32;&#43;&#32;&#92;&#99;&#100;&#111;&#116;&#115;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>is defined as the sum of the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Singular_value\">singular values<\/a> of a matrix. It is always larger than the Frobenius norm and is much larger when the singular values of <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;\"\/> decrease a slow rate. The matrix with the slowest-possible rate of singular decrease is the identity matrix. For this matrix, its Frobenius is <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-0d81eb812ea3f8dd1079d9d753571c7f_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#110;&#111;&#114;&#109;&#123;&#92;&#114;&#109;&#32;&#73;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#32;&#61;&#32;&#92;&#115;&#113;&#114;&#116;&#123;&#110;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"81\" style=\"vertical-align: -5px;\"\/>, and its nuclear norm is <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-d5b06e4947a607d08d607fe98bd157ac_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#110;&#111;&#114;&#109;&#123;&#92;&#114;&#109;&#32;&#73;&#125;&#95;&#42;&#32;&#61;&#32;&#110;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"64\" style=\"vertical-align: -5px;\"\/>\u2014a factor <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-0bbb71c94391d90ce47d108084081941_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#115;&#113;&#114;&#116;&#123;&#110;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"18\" width=\"25\" style=\"vertical-align: -4px;\"\/> larger!<\/p>\n\n\n\n<p>The conclusion of this discussion is that, for matrices with slowly decaying <a href=\"https:\/\/en.wikipedia.org\/wiki\/Eigenvalues_and_eigenvectors\">eigenvalues<\/a><sup class=\"modern-footnotes-footnote \" data-mfn=\"4\" data-mfn-post-scope=\"00000000000005840000000000000000_2247\"><a href=\"javascript:void(0)\"  role=\"button\" aria-pressed=\"false\" aria-describedby=\"mfn-content-00000000000005840000000000000000_2247-4\">4<\/a><\/sup><span id=\"mfn-content-00000000000005840000000000000000_2247-4\" role=\"tooltip\" class=\"modern-footnotes-footnote__note\" tabindex=\"0\" data-mfn=\"4\">Recall that the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Eigenvalues_and_eigenvectors\">eigenvalues<\/a> and <a href=\"https:\/\/en.wikipedia.org\/wiki\/Singular_value\">singular values<\/a> of a psd matrix coincide.<\/span>, the the randomized Nystr\u00f6m error bound (2) can be much larger than the randomized SVD error bound (1). For such problems, the error of the randomized SVD can be much smaller than the error of randomized Nystr\u00f6m approximation. We add this to our list of comparisons<\/p>\n\n\n\n<ol start=\"3\" class=\"wp-block-list\">\n<li><strong>Frobenius-norm error bounds?<\/strong> The (Frobenius-norm) error of the randomized SVD <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-a2d8df433995fe4d05fc1d5376d7f1dd_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#110;&#111;&#114;&#109;&#123;&#66;&#32;&#45;&#32;&#92;&#104;&#97;&#116;&#123;&#66;&#125;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"33\" width=\"77\" style=\"vertical-align: -12px;\"\/> is bounded in terms of the Frobenius-norm error of 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 <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-2e3b927f6f563f63aacda27b6b5a1dfc_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#110;&#111;&#114;&#109;&#123;&#66;&#32;&#45;&#32;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"20\" width=\"97\" style=\"vertical-align: -6px;\"\/> for <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-3b52155093f7415153fd3646d68574b1_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#114;&#32;&#92;&#97;&#112;&#112;&#114;&#111;&#120;&#32;&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"41\" style=\"vertical-align: 0px;\"\/>. For the Nystr\u00f6m approximation, the error <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-44837832ab88a3758df58c80fb1b15dc_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#110;&#111;&#114;&#109;&#123;&#65;&#32;&#45;&#32;&#92;&#104;&#97;&#116;&#123;&#65;&#125;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"33\" width=\"75\" style=\"vertical-align: -12px;\"\/> is bounded by a more complicated expression that also involves the <em>nuclear norm<\/em> of 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.<\/li>\n<\/ol>\n\n\n\n<h2 class=\"wp-block-heading\">Generalized Nystr\u00f6m Approximation: The Best of Both Worlds<\/h2>\n\n\n\n<p>It is natural to ask: Is there one algorithm that achieves the positive attributes of both the randomized Nystr\u00f6m and randomized SVD algorithms? Is there a single-pass low-rank approximation algorithm that can be applying to any rectangular matrix and achieves Frobenius-norm error bounds? The answer is yes, and we will derive such an approximation now.<\/p>\n\n\n\n<p>As with the randomized SVD and randomized Nystr\u00f6m approximation, we first compute the product <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;\"\/> 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;\"\/> with a 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;\"\/>. We may then search for the best approximation <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-79139b44e9e9de2bfd926e40dc6aaee7_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#104;&#97;&#116;&#123;&#66;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"18\" width=\"14\" style=\"vertical-align: 0px;\"\/> 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;\"\/> spanned by the columns 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;\"\/>. Such an approximation takes the form <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-a8de58e709de4241f12e6d1e478e5e82_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#104;&#97;&#116;&#123;&#66;&#125;&#32;&#61;&#32;&#89;&#87;\" title=\"Rendered by QuickLaTeX.com\" height=\"18\" width=\"71\" style=\"vertical-align: 0px;\"\/>, and we may find the best <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-676e51a51d2f41a64088aeb105e847e7_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#87;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"19\" style=\"vertical-align: 0px;\"\/> by solving a <a href=\"https:\/\/en.wikipedia.org\/wiki\/Least_squares\">least-squares<\/a> problem <p class=\"ql-center-displayed-equation\" style=\"line-height: 19px;\"><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-c10c5948a3d56992543344b0490d9a1a_l3.png\" height=\"19\" width=\"163\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#87;&#32;&#61;&#32;&#92;&#97;&#114;&#103;&#109;&#105;&#110;&#95;&#87;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#66;&#32;&#45;&#32;&#89;&#87;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#46;&#32;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>Symbolically, the solution to this problem may be written as <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-62fdb92cac1cbb2aa81aca00101a7597_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#87;&#32;&#61;&#32;&#89;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#66;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"78\" style=\"vertical-align: 0px;\"\/>, where <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;\"\/> is the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Moore\u2013Penrose_inverse\">Moore\u2013Penrose pseudoinverse<\/a>. The resulting low-rank approximation is <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-e3a5ea9bc069f0f92da6ef8966d04f22_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#104;&#97;&#116;&#123;&#66;&#125;&#32;&#61;&#32;&#89;&#40;&#89;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#66;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"23\" width=\"101\" style=\"vertical-align: -5px;\"\/>. In fact, this approximation coincides with the approximation generated by the randomized SVD algorithm. As with the standard randomized SVD, this approximation takes two passes over <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;\"\/> to form, one to 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;\"\/> and a second to form <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-62fdb92cac1cbb2aa81aca00101a7597_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#87;&#32;&#61;&#32;&#89;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#66;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"78\" style=\"vertical-align: 0px;\"\/>.<\/p>\n\n\n\n<p>To obtain a one-pass algorithm, we need a faster way of computing an (approximate) solution to the least-squares problem (3). As <a href=\"https:\/\/www.ethanepperly.com\/index.php\/2023\/11\/13\/does-sketching-work\/\">we<\/a> <a href=\"https:\/\/www.ethanepperly.com\/index.php\/2023\/11\/27\/which-sketch-should-i-use\/\">have<\/a> <a href=\"https:\/\/www.ethanepperly.com\/index.php\/2025\/02\/12\/note-to-self-how-accurate-is-sketch-and-solve\/\">seen<\/a> <a href=\"https:\/\/www.ethanepperly.com\/index.php\/2024\/11\/19\/note-to-self-sketch-and-solve-with-a-gaussian-embedding\/\">before<\/a> on this blog, <a href=\"https:\/\/www.ethanepperly.com\/index.php\/2023\/11\/13\/does-sketching-work\/\">sketching<\/a> provides a natural approach to quickly and approximately solving a least-squares problem. Specifically, we draw another random test matrix <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-b5cecc6189a2db53007b39cb67ec8eeb_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#80;&#104;&#105;&#32;&#92;&#105;&#110;&#32;&#92;&#114;&#101;&#97;&#108;&#94;&#123;&#110;&#92;&#116;&#105;&#109;&#101;&#115;&#32;&#112;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"14\" width=\"73\" style=\"vertical-align: -1px;\"\/> and solve the &#8220;sketched&#8221; least squares problem <p class=\"ql-center-displayed-equation\" style=\"line-height: 34px;\"><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-e07e026f85c1bc718d95c5c88a47d036_l3.png\" height=\"34\" width=\"227\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#104;&#97;&#116;&#123;&#87;&#125;&#32;&#61;&#32;&#92;&#97;&#114;&#103;&#109;&#105;&#110;&#95;&#87;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#92;&#80;&#104;&#105;&#94;&#92;&#116;&#111;&#112;&#32;&#66;&#32;&#45;&#32;&#40;&#92;&#80;&#104;&#105;&#94;&#92;&#116;&#111;&#112;&#32;&#89;&#41;&#87;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#46;&#32;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>For this approach to be effective, we need <em>oversampling<\/em>: the dimension <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;\"\/> of the sketching matrix <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-b5cecc6189a2db53007b39cb67ec8eeb_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#80;&#104;&#105;&#32;&#92;&#105;&#110;&#32;&#92;&#114;&#101;&#97;&#108;&#94;&#123;&#110;&#92;&#116;&#105;&#109;&#101;&#115;&#32;&#112;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"14\" width=\"73\" style=\"vertical-align: -1px;\"\/> such be larger than 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;\"\/>, e.g.. <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-fe53d632c91be8d77616f982ac08d346_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#112;&#32;&#61;&#32;&#50;&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"52\" style=\"vertical-align: -4px;\"\/>. The solution to (4) is <p class=\"ql-center-displayed-equation\" style=\"line-height: 24px;\"><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-bdf37e0344474a81247242dc1fbc106f_l3.png\" height=\"24\" width=\"154\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#104;&#97;&#116;&#123;&#87;&#125;&#32;&#61;&#32;&#40;&#92;&#80;&#104;&#105;&#94;&#92;&#116;&#111;&#112;&#32;&#89;&#41;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#40;&#92;&#80;&#104;&#105;&#94;&#92;&#116;&#111;&#112;&#32;&#66;&#41;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>and the low-rank approximation is <p class=\"ql-center-displayed-equation\" style=\"line-height: 24px;\"><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-e2fdc92bd90711c249030489953513de_l3.png\" height=\"24\" width=\"357\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#104;&#97;&#116;&#123;&#66;&#125;&#32;&#61;&#32;&#89;&#40;&#92;&#80;&#104;&#105;&#94;&#92;&#116;&#111;&#112;&#32;&#89;&#41;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#40;&#92;&#80;&#104;&#105;&#94;&#92;&#116;&#111;&#112;&#32;&#66;&#41;&#32;&#61;&#32;&#40;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#41;&#32;&#40;&#92;&#80;&#104;&#105;&#94;&#92;&#116;&#111;&#112;&#32;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#41;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#40;&#92;&#80;&#104;&#105;&#94;&#92;&#116;&#111;&#112;&#32;&#66;&#41;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>This type of approximation is called a <em>generalized Nystr\u00f6m approximation<\/em>, and it can be computed in a single pass over <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;\"\/>. (Namely, one should acquire\u2014in the <em>same<\/em> pass\u2014the products <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;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-a6cd604e5040000f8794a876d1de6aa0_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#80;&#104;&#105;&#94;&#92;&#116;&#111;&#112;&#32;&#66;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"38\" style=\"vertical-align: 0px;\"\/>.) The generalized Nystr\u00f6m approximation also satisfies our other desired properties, applying to general, rectangular matrix and, as we will see, achieving Frobenius-norm approximation error.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">History<\/h2>\n\n\n\n<p>In the modern randomized linear algebra literature, the generalized Nystr\u00f6m approximation appears to have been concurrently discovered by <a href=\"https:\/\/doi.org\/10.1016\/j.acha.2007.12.002\">Woolfe, Liberty, Rokhlin, &amp; Tygert (2008)<\/a> and <a href=\"https:\/\/www.cs.cmu.edu\/afs\/cs\/user\/dwoodruf\/www\/cw09.pdf\">Clarkson &amp; Woodruff (2009)<\/a>. An algebraically equivalent but more numerically stable version of the generalized Nystr\u00f6m approximation was developed by <a href=\"https:\/\/arxiv.org\/abs\/1609.00048\">Tropp, Yurtsever, Udell, &amp; Cevher (2017)<\/a>. <a href=\"https:\/\/arxiv.org\/abs\/2009.11392\">Nakatsukasa (2020)<\/a> re-examined the low-rank approximation format, developed a different class of numerical stable implementations, and suggested the name generalized Nystr\u00f6m approximation. Alex Townsend and Per-Gunnar Martinsson trace the origins of this low-rank approximation format far earlier back to the works of Wedderburn (1934).<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Implementation<\/h2>\n\n\n\n<p>This post is concerned with the generalized Nystr\u00f6m approximation as a type of <em>low-rank approximation format<\/em>. To use generalized Nystr\u00f6m approximation in practice, one must use an appropriate <em>algorithm<\/em> which computes the decomposition in a stable way.<\/p>\n\n\n\n<p>Perhaps the simplest algorithm for computing a generalized Nystr\u00f6m approximation was studied by <a href=\"https:\/\/arxiv.org\/abs\/2009.11392\">Nakatsukasa (2020)<\/a>. One begins by computing the matrices <p class=\"ql-center-displayed-equation\" style=\"line-height: 21px;\"><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-d95eee60a18e0b58b304b250ab7f3b0f_l3.png\" height=\"21\" width=\"269\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#89;&#32;&#61;&#32;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#44;&#32;&#92;&#113;&#117;&#97;&#100;&#32;&#90;&#32;&#61;&#32;&#66;&#94;&#92;&#116;&#111;&#112;&#32;&#92;&#79;&#109;&#101;&#103;&#97;&#44;&#32;&#92;&#113;&#117;&#97;&#100;&#32;&#67;&#32;&#61;&#32;&#92;&#80;&#104;&#105;&#94;&#92;&#116;&#111;&#112;&#32;&#89;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>Then, to represent the generalized Nystr\u00f6m approximation <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-79139b44e9e9de2bfd926e40dc6aaee7_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#104;&#97;&#116;&#123;&#66;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"18\" width=\"14\" style=\"vertical-align: 0px;\"\/> as a factored matrix, one takes a <a href=\"https:\/\/en.wikipedia.org\/wiki\/QR_decomposition\">QR decomposition<\/a> <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-38c49f1fc6f9ca163f7cc888b5a0deb1_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#67;&#32;&#61;&#32;&#81;&#82;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"66\" style=\"vertical-align: -4px;\"\/> and defines <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-0de0d9068249ab04f5df009aa1a275cc_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#70;&#32;&#61;&#32;&#89;&#82;&#94;&#123;&#45;&#49;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"82\" style=\"vertical-align: 0px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-87ec2b6e86097ea001b360a4334442f6_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#71;&#32;&#61;&#32;&#90;&#81;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"65\" style=\"vertical-align: -4px;\"\/>. The generalized Nystr\u00f6m approximation has been computed in factored form: <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-70055519d8c6dfe1e2d4ac26b174729c_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#104;&#97;&#116;&#123;&#66;&#125;&#32;&#61;&#32;&#70;&#71;&#94;&#92;&#116;&#111;&#112;\" title=\"Rendered by QuickLaTeX.com\" height=\"18\" width=\"76\" style=\"vertical-align: 0px;\"\/>. In cases where the core matrix <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;\"\/> is <a href=\"https:\/\/en.wikipedia.org\/wiki\/Rank_(linear_algebra)#Computation\">rank-deficient up to machine precision<\/a>, the numerical stability of this procedure can sometimes be aided by using a <a href=\"https:\/\/en.wikipedia.org\/wiki\/Singular_value_decomposition#Truncated_SVD\">truncated SVD<\/a> or <a href=\"https:\/\/en.wikipedia.org\/wiki\/QR_decomposition#Column_pivoting\">column-pivoted QR decomposition<\/a> of <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;\"\/>; see <a href=\"https:\/\/arxiv.org\/abs\/2009.11392\">Nakatsukasa&#8217;s paper<\/a> for details. An alternate implementation which outputs <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-79139b44e9e9de2bfd926e40dc6aaee7_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#104;&#97;&#116;&#123;&#66;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"18\" width=\"14\" style=\"vertical-align: 0px;\"\/> as a compact SVD was developed by <a href=\"https:\/\/arxiv.org\/abs\/1609.00048\">Tropp, Yurtsever, Udell, and Cevher (2017)<\/a>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Relationship to Other Formats<\/h2>\n\n\n\n<p>As the name suggests, the generalized Nystr\u00f6m approximation format generalizes the Nystr\u00f6m approximation beyond psd matrices. Indeed, the standard Nystr\u00f6m approximation <p class=\"ql-center-displayed-equation\" style=\"line-height: 24px;\"><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-fb7ae8960f8c0173063c23f7290a1b63_l3.png\" height=\"24\" width=\"198\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#104;&#97;&#116;&#123;&#65;&#125;&#32;&#61;&#32;&#40;&#65;&#92;&#79;&#109;&#101;&#103;&#97;&#41;&#32;&#40;&#92;&#79;&#109;&#101;&#103;&#97;&#94;&#92;&#116;&#111;&#112;&#32;&#65;&#32;&#92;&#79;&#109;&#101;&#103;&#97;&#41;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#40;&#92;&#79;&#109;&#101;&#103;&#97;&#94;&#92;&#116;&#111;&#112;&#32;&#65;&#41;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>is precisely the generalized Nystr\u00f6m approximation of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-11f4f587954b361e7d78940f65b8d70d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"13\" style=\"vertical-align: 0px;\"\/> with a test matrix <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-419d6208877869e57f8b01baf44f7367_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#79;&#109;&#101;&#103;&#97;&#32;&#61;&#32;&#92;&#80;&#104;&#105;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"48\" style=\"vertical-align: 0px;\"\/>.<\/p>\n\n\n\n<p>Perhaps less obviously, the generalized Nystr\u00f6m approximation also generalizes the randomized SVD approximation. Indeed, the randomized SVD approximation <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-a85f3c69dfa18109723d9b5360839ead_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#104;&#97;&#116;&#123;&#66;&#125;&#32;&#61;&#32;&#40;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#41;&#40;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#41;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#66;\" title=\"Rendered by QuickLaTeX.com\" height=\"23\" width=\"141\" style=\"vertical-align: -5px;\"\/> is the generalized Nystr\u00f6m approximation with trivial right test matrix <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-79d6bd4d41d6dab6ba7b599b6b4f637d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#80;&#104;&#105;&#32;&#61;&#32;&#73;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"45\" style=\"vertical-align: 0px;\"\/>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Generalized Nystr\u00f6m Approximation = Sketch-and-Solve + Randomized SVD<\/h2>\n\n\n\n<p>What <em>is<\/em> the generalized Nystr\u00f6m approximation? There are several interpretations. For instance, if <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-6ba46c0cdca8b6bafa0f633381f79d7f_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#112;&#32;&#61;&#32;&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"43\" style=\"vertical-align: -4px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-eb396e9c8adc0c92e5159e1e4014d623_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#80;&#104;&#105;&#94;&#92;&#116;&#111;&#112;&#32;&#66;&#32;&#92;&#79;&#109;&#101;&#103;&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"51\" style=\"vertical-align: 0px;\"\/> is invertible, the generalized Nystr\u00f6m approximation is the unique approximation satisfying the <em>interpolatory condition<\/em> <p class=\"ql-center-displayed-equation\" style=\"line-height: 20px;\"><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-ed39d951ca827f023b0460fce18b1e0a_l3.png\" height=\"20\" width=\"247\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#104;&#97;&#116;&#123;&#66;&#125;&#92;&#79;&#109;&#101;&#103;&#97;&#32;&#61;&#32;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#32;&#92;&#113;&#117;&#97;&#100;&#32;&#92;&#116;&#101;&#120;&#116;&#123;&#97;&#110;&#100;&#125;&#32;&#92;&#113;&#117;&#97;&#100;&#32;&#92;&#104;&#97;&#116;&#123;&#66;&#125;&#94;&#92;&#116;&#111;&#112;&#92;&#80;&#104;&#105;&#32;&#61;&#32;&#66;&#94;&#92;&#116;&#111;&#112;&#92;&#80;&#104;&#105;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>Notwithstanding the validity and usefulness of other interpretations, my view is that the <em>most useful<\/em> interpretation of generalized Nystr\u00f6m approximation is the one we started with:<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p>Generalized Nystr\u00f6m approximation is a sketched version of the randomized SVD approximation.<\/p>\n<\/blockquote>\n\n\n\n<p>To see this insight in action, we will use it to analyze the generalized Nystr\u00f6m approximation with Gaussian test matrices. Let <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-1c6c6010558b60dad9a7eaaa0473e8e7_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#79;&#109;&#101;&#103;&#97;&#32;&#92;&#105;&#110;&#32;&#92;&#114;&#101;&#97;&#108;&#94;&#123;&#110;&#92;&#116;&#105;&#109;&#101;&#115;&#32;&#107;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"73\" style=\"vertical-align: -1px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-b5cecc6189a2db53007b39cb67ec8eeb_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#80;&#104;&#105;&#32;&#92;&#105;&#110;&#32;&#92;&#114;&#101;&#97;&#108;&#94;&#123;&#110;&#92;&#116;&#105;&#109;&#101;&#115;&#32;&#112;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"14\" width=\"73\" style=\"vertical-align: -1px;\"\/> be populated with independent standard Gaussian random entries, and as we have been, assume <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-a08f39d4eed525cedbdc9ca29c3f39e2_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#112;&#92;&#103;&#101;&#32;&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"43\" style=\"vertical-align: -4px;\"\/>. Let us analyze the expected (squared) Frobenius-norm error of the generalized Nystr\u00f6m approximation.<\/p>\n\n\n\n<p>We will use the following result for sketching with a Gaussian embedding, due to <a href=\"https:\/\/arxiv.org\/abs\/2002.06538\">Bartan &amp; Pilanci (2020)<\/a> and discussed in <a href=\"https:\/\/www.ethanepperly.com\/index.php\/2024\/11\/19\/note-to-self-sketch-and-solve-with-a-gaussian-embedding\/\">this previous blog post<\/a>.<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p><strong>Theorem 1 (sketch-and-solve):<\/strong> Consider a (matrix) least-squares problem <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-1fbec03b765e920f2546d70acc1e315d_l3.png\" height=\"22\" width=\"213\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#87;&#32;&#61;&#32;&#89;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#66;&#61;&#32;&#92;&#97;&#114;&#103;&#109;&#105;&#110;&#95;&#87;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#66;&#32;&#45;&#32;&#89;&#87;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>with dimensions <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-f369e5d1fa0651eedfa70b6c68821b7a_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#89;&#32;&#92;&#105;&#110;&#32;&#92;&#114;&#101;&#97;&#108;&#94;&#123;&#110;&#32;&#92;&#116;&#105;&#109;&#101;&#115;&#32;&#107;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"75\" style=\"vertical-align: -1px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-ec291d90d0125a3b8ab19d6b52b2d5f6_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#66;&#32;&#92;&#105;&#110;&#32;&#92;&#114;&#101;&#97;&#108;&#94;&#123;&#110;&#92;&#116;&#105;&#109;&#101;&#115;&#32;&#110;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"14\" width=\"76\" style=\"vertical-align: -1px;\"\/>. Let <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-b5cecc6189a2db53007b39cb67ec8eeb_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#80;&#104;&#105;&#32;&#92;&#105;&#110;&#32;&#92;&#114;&#101;&#97;&#108;&#94;&#123;&#110;&#92;&#116;&#105;&#109;&#101;&#115;&#32;&#112;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"14\" width=\"73\" style=\"vertical-align: -1px;\"\/> be a (standard) Gaussian test matrix, and instate the <a href=\"https:\/\/www.ethanepperly.com\/index.php\/2023\/11\/13\/does-sketching-work\/#how-can-you-use-sketching\">sketch-and-solve<\/a> solution <p class=\"ql-center-displayed-equation\" style=\"line-height: 34px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-47453e73c76d516332da7709bec4fdf2_l3.png\" height=\"34\" width=\"349\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#104;&#97;&#116;&#123;&#87;&#125;&#32;&#61;&#32;&#40;&#92;&#80;&#104;&#105;&#94;&#92;&#116;&#111;&#112;&#32;&#89;&#41;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#92;&#80;&#104;&#105;&#94;&#92;&#116;&#111;&#112;&#32;&#66;&#32;&#61;&#32;&#92;&#97;&#114;&#103;&#109;&#105;&#110;&#95;&#87;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#92;&#80;&#104;&#105;&#94;&#92;&#116;&#111;&#112;&#32;&#66;&#32;&#45;&#32;&#40;&#92;&#80;&#104;&#105;&#94;&#92;&#116;&#111;&#112;&#32;&#89;&#41;&#87;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>Then <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-1dd58766c5711cb52838468de28f2956_l3.png\" height=\"43\" width=\"624\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#101;&#120;&#112;&#101;&#99;&#116;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#66;&#32;&#45;&#32;&#89;&#92;&#104;&#97;&#116;&#123;&#87;&#125;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#32;&#61;&#32;&#92;&#101;&#120;&#112;&#101;&#99;&#116;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#66;&#32;&#45;&#32;&#89;&#40;&#92;&#80;&#104;&#105;&#94;&#92;&#116;&#111;&#112;&#32;&#89;&#41;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#92;&#80;&#104;&#105;&#94;&#92;&#116;&#111;&#112;&#32;&#66;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#32;&#61;&#32;&#92;&#108;&#101;&#102;&#116;&#40;&#32;&#49;&#32;&#43;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#107;&#125;&#123;&#112;&#32;&#45;&#32;&#40;&#107;&#43;&#49;&#41;&#125;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#41;&#92;&#110;&#111;&#114;&#109;&#123;&#66;&#32;&#45;&#32;&#89;&#89;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#66;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n<\/blockquote>\n\n\n\n<p>We can apply this result to the generalized Nystr\u00f6m approximation by setting <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;\"\/>. Let <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-ce68157b02a26da4fdf9589cf0e2a196_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#101;&#120;&#112;&#101;&#99;&#116;&#95;&#123;&#92;&#80;&#104;&#105;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"22\" style=\"vertical-align: -3px;\"\/> denote the expectation over <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-424bd40d641ff720e56eece2ff4a8352_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#80;&#104;&#105;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"12\" style=\"vertical-align: 0px;\"\/> alone. Then <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-3ca90719321990c2e97c775f86238ce7_l3.png\" height=\"43\" width=\"577\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#101;&#120;&#112;&#101;&#99;&#116;&#95;&#92;&#80;&#104;&#105;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#66;&#32;&#45;&#32;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#40;&#92;&#80;&#104;&#105;&#94;&#92;&#116;&#111;&#112;&#32;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#41;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#92;&#80;&#104;&#105;&#94;&#92;&#116;&#111;&#112;&#32;&#66;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#32;&#61;&#32;&#92;&#108;&#101;&#102;&#116;&#40;&#32;&#49;&#32;&#43;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#107;&#125;&#123;&#112;&#32;&#45;&#32;&#40;&#107;&#32;&#43;&#32;&#49;&#41;&#125;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#41;&#92;&#110;&#111;&#114;&#109;&#123;&#66;&#32;&#45;&#32;&#40;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#41;&#40;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#41;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#66;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>But <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-bdf85e310f2562c8fecad624d738f8c4_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#40;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#41;&#40;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#41;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#66;\" title=\"Rendered by QuickLaTeX.com\" height=\"20\" width=\"102\" style=\"vertical-align: -5px;\"\/> is just the randomized SVD approximation. Invoking the randomized SVD bound (1) yields <p class=\"ql-center-displayed-equation\" style=\"line-height: 141px;\"><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-f6a0cfb074737e67fcb3b172f5d5badc_l3.png\" height=\"141\" width=\"709\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#98;&#101;&#103;&#105;&#110;&#123;&#97;&#108;&#105;&#103;&#110;&#42;&#125;&#92;&#101;&#120;&#112;&#101;&#99;&#116;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#66;&#32;&#45;&#32;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#40;&#92;&#80;&#104;&#105;&#94;&#92;&#116;&#111;&#112;&#32;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#41;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#92;&#80;&#104;&#105;&#94;&#92;&#116;&#111;&#112;&#32;&#66;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#32;&#38;&#61;&#32;&#92;&#101;&#120;&#112;&#101;&#99;&#116;&#95;&#92;&#79;&#109;&#101;&#103;&#97;&#92;&#108;&#101;&#102;&#116;&#091;&#92;&#101;&#120;&#112;&#101;&#99;&#116;&#95;&#92;&#80;&#104;&#105;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#66;&#32;&#45;&#32;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#40;&#92;&#80;&#104;&#105;&#94;&#92;&#116;&#111;&#112;&#32;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#41;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#92;&#80;&#104;&#105;&#94;&#92;&#116;&#111;&#112;&#32;&#66;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#92;&#114;&#105;&#103;&#104;&#116;&#093;&#32;&#92;&#92;&#38;&#61;&#32;&#92;&#108;&#101;&#102;&#116;&#40;&#32;&#49;&#32;&#43;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#107;&#125;&#123;&#112;&#32;&#45;&#32;&#40;&#107;&#32;&#43;&#32;&#49;&#41;&#125;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#41;&#92;&#101;&#120;&#112;&#101;&#99;&#116;&#95;&#92;&#79;&#109;&#101;&#103;&#97;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#66;&#32;&#45;&#32;&#40;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#41;&#40;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#41;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#66;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#32;&#92;&#92;&#38;&#92;&#108;&#101;&#32;&#92;&#108;&#101;&#102;&#116;&#40;&#32;&#49;&#32;&#43;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#107;&#125;&#123;&#112;&#32;&#45;&#32;&#40;&#107;&#32;&#43;&#32;&#49;&#41;&#125;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#41;&#92;&#108;&#101;&#102;&#116;&#091;&#92;&#109;&#105;&#110;&#95;&#123;&#114;&#32;&#60;&#32;&#107;&#45;&#49;&#125;&#92;&#108;&#101;&#102;&#116;&#40;&#32;&#49;&#32;&#43;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#114;&#125;&#123;&#107;&#32;&#45;&#32;&#40;&#114;&#32;&#43;&#32;&#49;&#41;&#125;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#41;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#66;&#32;&#45;&#32;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#92;&#114;&#105;&#103;&#104;&#116;&#093;&#46;&#92;&#101;&#110;&#100;&#123;&#97;&#108;&#105;&#103;&#110;&#42;&#125;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>Voil\u00e0! We have obtained explicit bounds for the generalized Nystr\u00f6m method with little effort. We record this result as a theorem:<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p><strong>Theorem 2 (generalized Nystr\u00f6m approximation):<\/strong> With the present setting, it holds that <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-be78edd2761af9a1cc467056a24c73e9_l3.png\" height=\"43\" width=\"709\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#101;&#120;&#112;&#101;&#99;&#116;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#66;&#32;&#45;&#32;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#40;&#92;&#80;&#104;&#105;&#94;&#92;&#116;&#111;&#112;&#32;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#41;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#92;&#80;&#104;&#105;&#94;&#92;&#116;&#111;&#112;&#32;&#66;&#125;&#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;&#112;&#32;&#45;&#32;&#40;&#107;&#32;&#43;&#32;&#49;&#41;&#125;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#41;&#92;&#108;&#101;&#102;&#116;&#091;&#92;&#109;&#105;&#110;&#95;&#123;&#114;&#32;&#60;&#32;&#107;&#45;&#49;&#125;&#92;&#108;&#101;&#102;&#116;&#40;&#32;&#49;&#32;&#43;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#114;&#125;&#123;&#107;&#32;&#45;&#32;&#40;&#114;&#32;&#43;&#32;&#49;&#41;&#125;&#32;&#92;&#114;&#105;&#103;&#104;&#116;&#41;&#32;&#92;&#110;&#111;&#114;&#109;&#123;&#66;&#32;&#45;&#32;&#92;&#108;&#111;&#119;&#114;&#97;&#110;&#107;&#123;&#66;&#125;&#95;&#114;&#125;&#95;&#123;&#92;&#114;&#109;&#32;&#70;&#125;&#94;&#50;&#92;&#114;&#105;&#103;&#104;&#116;&#093;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n<\/blockquote>\n\n\n\n<p>This result is Theorem 4.3 in this paper of <a href=\"https:\/\/arxiv.org\/abs\/1609.00048\">Tropp, Yurtsever, Udell, &amp; Cevher (2017)<\/a>. A slight refinement of this bound appears <a href=\"https:\/\/arxiv.org\/abs\/2605.19096\">in my paper with Robert Webber<\/a>, and we show that our new bound is sharp on hard examples. Thus, Theorem 2 is nearly the best possible error bound for the generalized Nystr\u00f6m approximation.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Choice of Random Matrix<\/h2>\n\n\n\n<p>For most of this post, we have focused on the cases where the random test 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;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-424bd40d641ff720e56eece2ff4a8352_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#80;&#104;&#105;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"12\" style=\"vertical-align: 0px;\"\/> are unstructured matrices with Gaussian random entries. But <a href=\"https:\/\/www.ethanepperly.com\/index.php\/2023\/11\/27\/which-sketch-should-i-use\/\">can we use more structured random test matrices<\/a>? Say, <a href=\"https:\/\/www.ethanepperly.com\/index.php\/2020\/07\/18\/big-ideas-in-applied-math-sparse-matrices\/\">sparse<\/a> test matrices? Do these lead to faster low-rank approximation algorithms?<\/p>\n\n\n\n<p>For the randomized SVD, the results are disappointing. Computing <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;\"\/> with a sparse random matrix is fast. But then we compute <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-7091d39cfaffa05f12484351d335dca7_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#81;&#32;&#61;&#32;&#92;&#111;&#112;&#101;&#114;&#97;&#116;&#111;&#114;&#110;&#97;&#109;&#101;&#123;&#111;&#114;&#116;&#104;&#125;&#40;&#89;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"97\" style=\"vertical-align: -5px;\"\/> and compute <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-0034ee65a44d2963c4f0c0697ea10b1a_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#67;&#32;&#61;&#32;&#81;&#94;&#92;&#116;&#111;&#112;&#32;&#66;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"77\" style=\"vertical-align: -4px;\"\/>; the matrix <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;\"\/> is dense and unstructured, so computing <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-0034ee65a44d2963c4f0c0697ea10b1a_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#67;&#32;&#61;&#32;&#81;&#94;&#92;&#116;&#111;&#112;&#32;&#66;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"77\" style=\"vertical-align: -4px;\"\/> is slower and all benefits of the sparse test matrix have been erased.<\/p>\n\n\n\n<p>The issue with the randomized SVD is that it&#8217;s a two-pass algorithm: The first pass, computing <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;\"\/>, can be done using a sparse random test matrix. But the second pass <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-8dba5ca0d8880af6cb4b15cfdf65d0d6_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#81;&#94;&#92;&#116;&#111;&#112;&#32;&#66;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"40\" style=\"vertical-align: -4px;\"\/> requires a matrix product with a dense matrix <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;\"\/>.<\/p>\n\n\n\n<p>The situation is much better for the generalized Nystr\u00f6m approximation, which requires only a single pass and can be implemented only by multiplying <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;\"\/> against sparse matrices. Indeed, generating <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;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-424bd40d641ff720e56eece2ff4a8352_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#80;&#104;&#105;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"12\" style=\"vertical-align: 0px;\"\/> to be sparse matrices, the generalized Nystr\u00f6m approximation can be written <p class=\"ql-center-displayed-equation\" style=\"line-height: 24px;\"><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-959c9e287d25f46bd1011f38affcab7b_l3.png\" height=\"24\" width=\"351\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#091;&#92;&#104;&#97;&#116;&#123;&#66;&#125;&#32;&#61;&#32;&#89;&#40;&#92;&#80;&#104;&#105;&#94;&#42;&#32;&#89;&#41;&#94;&#92;&#100;&#97;&#103;&#103;&#101;&#114;&#32;&#90;&#32;&#92;&#113;&#117;&#97;&#100;&#32;&#92;&#116;&#101;&#120;&#116;&#123;&#102;&#111;&#114;&#32;&#125;&#32;&#89;&#32;&#61;&#32;&#66;&#92;&#79;&#109;&#101;&#103;&#97;&#32;&#92;&#116;&#101;&#120;&#116;&#123;&#32;&#97;&#110;&#100;&#32;&#125;&#32;&#90;&#32;&#61;&#32;&#92;&#80;&#104;&#105;&#94;&#92;&#116;&#111;&#112;&#32;&#66;&#46;&#92;&#093;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p>We see that the only interaction we need with the matrix <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;\"\/> has been isolated into matrix products with the random test matrices, and we obtain speedups by replacing using sparse random test matrices for <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;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.ethanepperly.com\/wp-content\/ql-cache\/quicklatex.com-424bd40d641ff720e56eece2ff4a8352_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#80;&#104;&#105;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"12\" style=\"vertical-align: 0px;\"\/>.<\/p>\n\n\n\n<p>Structured test matrices, like sparse ones, <a href=\"https:\/\/www.ethanepperly.com\/index.php\/2023\/11\/27\/which-sketch-should-i-use\/\">can be very powerful<\/a>. But basic theoretical questions remain about their properties. We tackle these theoretical questions in <a href=\"https:\/\/arxiv.org\/abs\/2508.21189\">my new paper (joint with Chris Cama\u00f1o, Raphael Meyer, and Joel Tropp)<\/a>, and we provide experiments demonstrating how structured sketching matrices can lead to large speedups in generalized Nystr\u00f6m approximation and other linear algebra tasks. I think it&#8217;s a really neat paper, and my wonderful collaborator Chris did some really beautiful experiments for it. I hope you&#8217;ll check it out!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Today, I want to talk about the generalized Nystr\u00f6m approximation, which I regard as the one of the &#8220;big three&#8221; approaches to constructing a low-rank approximation to matrix. Understanding this approximation, under what conditions it works and the sharpest possible error bounds for it, is a subject of two recent papers of mine: On the<a class=\"more-link\" href=\"https:\/\/www.ethanepperly.com\/index.php\/2026\/05\/20\/low-rank-approximation-toolbox-generalized-nystrom-approximation\/\">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,12],"tags":[],"class_list":["post-2247","post","type-post","status-publish","format-standard","hentry","category-low-rank-approximation-toolbox","category-sketching"],"_links":{"self":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts\/2247","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=2247"}],"version-history":[{"count":5,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts\/2247\/revisions"}],"predecessor-version":[{"id":2324,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts\/2247\/revisions\/2324"}],"wp:attachment":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/media?parent=2247"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/categories?post=2247"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/tags?post=2247"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}