{"id":1777,"date":"2024-11-19T22:13:03","date_gmt":"2024-11-19T22:13:03","guid":{"rendered":"https:\/\/www.ethanepperly.com\/?p=1777"},"modified":"2024-11-21T16:52:35","modified_gmt":"2024-11-21T16:52:35","slug":"note-to-self-sketch-and-solve-with-a-gaussian-embedding","status":"publish","type":"post","link":"https:\/\/www.ethanepperly.com\/index.php\/2024\/11\/19\/note-to-self-sketch-and-solve-with-a-gaussian-embedding\/","title":{"rendered":"Note to Self: Sketch-and-Solve with a Gaussian Embedding"},"content":{"rendered":"\n

In the comments to my post Does Sketching Work?<\/em><\/a>, I was asked a very interesting question, which I will paraphrase as follows:<\/p>\n\n\n\n

\n

Is the sketch-and-solve<\/a> least-squares solution \"\hat{x} = \operatorname*{argmin}_{\hat{x}} \norm{(SA)\hat{x} - Sb}\" an unbiased estimate<\/a> of the true least squares solution<\/a> of \"x = \operatorname*{argmin}_x \norm{Ax - b}\"?<\/p>\n<\/blockquote>\n\n\n\n

In this post, I will answer this question for the special case in which \"S\" is a Gaussian sketch, and I will also compute the expected least-squares residual \"\expect \norm{A\hat{x}-b}^2\". Throughout this post, I will assume knowledge of sketching; see my previous two<\/a> posts<\/a> for a refresher if needed. For this post, \"A\" will have dimensions \"n\times d\" and \"S\" will have dimensions \"\ell\times n\", and these parameters are related \"n\ge \ell \ge d\".<\/p>\n\n\n\n

I thought I knew the answer to this question\u2014that sketch-and-solve suffers from inversion bias<\/a><\/em>. Indeed, the fact I remembered is that

(1) <\/span>   <\/span>\"\[\expect\Big[\big((SA)^\top (SA)\big)^{-1}\Big] \ne \big(A^\top A\big)^{-1}\]\"<\/p>for the sketching matrices \"S\" in common use. The issue of the inversion bias (1) is discussed in this paper<\/a>.<\/p>\n\n\n\n

However, the inversion bias (1) does not<\/em> imply that sketch-and-solve is biased. In fact, for a Gaussian sketch1<\/a><\/sup>Note that, typically, we use a sketch \"S\" where the variance of the entries is \"1/d\". The sketch-and-solve solution \"(SA)^\dagger (Sb)\" does not change under a scaling of the matrix \"S\". Thus, we are free to take the entries to have variance one.<\/span>

(2) <\/span>   <\/span>\"\[S \in \real^{\ell\times n} \quad \text{with } S_{ij} \sim \text{Normal}(0,1) \text{ iid},\]\"<\/p>sketch-and-solve is unbiased<\/em>.<\/p>\n\n\n\n

\n

Theorem (Gaussian sketch-and-solve is unbiased).<\/strong> Let \"S\" be a Gaussian sketch (2) and let \"A \in \real^{n\times d}\" be a full column-rank matrix. Then

(3) <\/span>   <\/span>\"\[\expect[(SA)^\dagger(Sb)] = A^\dagger b. \]\"<\/p>That is, the sketch-and-solve solution \"(SA)^\dagger(Sb)\" is an unbiased estimate for the least-squares solution \"A^\dagger b\".<\/p>\n<\/blockquote>\n\n\n\n

Here, \"{}^\dagger\" is the Moore\u2013Penrose pseudoinverse, which effectuates the least-squares solution:

  <\/span>   <\/span>\"\[A^\dagger b = \operatorname*{argmin}_{x\in\real^d} \norm{Ax - b}.\]\"<\/p>In particular, by the normal equations, we have the relation

(4) <\/span>   <\/span>\"\[A^\dagger = (A^\top A)^{-1} A^\top,\]\"<\/p>valid for any matrix \"A\" with full column-rank.<\/p>\n\n\n\n

Let us prove this theorem. The Gaussian sketch (1) is orthogonally invariant: that is, \"V^\top SU\" has the same distribution as \"S\" for any orthogonal matrices \"U\" and \"V\". Thus, we are free to reparametrize. Let

  <\/span>   <\/span>\"\[A = U\twobyone{\Sigma}{0}V^\top\]\"<\/p>be a (full) singular value decomposition of \"A\". Make the changes of variables

  <\/span>   <\/span>\"\[A \mapsto U^\top A V, \quad S \mapsto V^\top SU, \quad b \mapsto U^\top b.\]\"<\/p>After this change of variables, \"S\" still has the same distribution (2) and

  <\/span>   <\/span>\"\[A = \twobyone{\Sigma}{0}.\]\"<\/p>Partition the reparametrized \"b\" and \"S\" conformally with \"A\":

  <\/span>   <\/span>\"\[b = \twobyone{b_1}{b_2}, \quad S = \onebytwo{S_1}{S_2}.\]\"<\/p>Under this change of variables, the least-squares solution is

(5) <\/span>   <\/span>\"\[A^\dagger b = \Sigma^{-1}b_1.\]\"<\/p><\/p>\n\n\n\n

Now, we are ready to prove the claim (3). Observe that \"SA = S_1\Sigma\". Begin by using the normal equations (4) to write out the sketch-and-solve solution

  <\/span>   <\/span>\"\[(SA)^\dagger (Sb) = [(SA)^\top (SA)]^{-1}(SA)^\top (Sb).\]\"<\/p>Observe that \"SA = S_1\Sigma\". Thus,

  <\/span>   <\/span>\"\[(SA)^\dagger (Sb) = [\Sigma S_1^\top S_1\Sigma]^{-1}\Sigma S_1^\top \onebytwo{S_1}{S_2}\twobyone{b_1}{b_2}.\]\"<\/p>Simplify to obtain

  <\/span>   <\/span>\"\[(SA)^\dagger (Sb) = \Sigma^{-1}(S_1^\top S_1)^{-1} S_1^\top (S_1b_1 + S_2 b_2).\]\"<\/p>Using the normal equations (4) and the solution formula (5), we obtain

(6) <\/span>   <\/span>\"\[(SA)^\dagger (Sb) = \Sigma^{-1}b_1 + \Sigma^{-1} S_1^\dagger S_2b_2 = A^\dagger b + \Sigma^{-1} S_1^\dagger S_2b_2. \]\"<\/p>By the definition (2) of \"S\", \"S_1\" and \"S_2\" are independent and \"\expect[S_2] = 0\". Thus, taking expectations, we obtain

  <\/span>   <\/span>\"\[\expect[(SA)^\dagger (Sb)] = A^\dagger b + \Sigma^{-1} \expect[S_1^\dagger] \expect[S_2]b_2 = A^\dagger b.\]\"<\/p>The desired claim (3) is proven.<\/p>\n\n\n\n

Note that the solution formula (6) holds for any<\/em> sketching matrix \"S\". We only use Gaussianity at the last step, where we invoke three properties (1) \"S\" is mean zero; (2) \"S\" is orthogonally invariant; and (3) conditional on the first \"d\" columns of \"S\", the last \"n-d\" columns of \"S\" are mean-zero.<\/p>\n\n\n\n

The Least-Squares Residual for Gaussian Sketch-and-Solve<\/h2>\n\n\n\n

The solution formula (6) can be used to understand other properties of the Gaussian sketch-and-solve solution. In this section, we use (6) to understand the expected squared residual norm

  <\/span>   <\/span>\"\[\expect \norm{A\hat{x} - b}^2,\]\"<\/p>where \"\hat{x} = (SA)^\dagger (Sb)\" is the sketch-and-solve solution. We write the expected residual norm as

  <\/span>   <\/span>\"\[\expect\norm{A\hat{x} - b}^2 = \expect\norm{\twobyone{b_1 + S_1^\dagger S_2b_2}{0} - \twobyone{b_1}{b_2}}^2 = \norm{b_2}^2 + \expect\norm{S_1^\dagger S_2b_2}^2.\]\"<\/p>Now, use the Gaussian\u2013inverse Gaussian matrix product formula<\/a> to compute the expectation, obtaining

  <\/span>   <\/span>\"\[\expect\norm{A\hat{x} - b}^2 = \left(1+\frac{d}{\ell-d-1}\right)\norm{b_2}^2.\]\"<\/p>Finally, we recognize \"\norm{b_2}\" is the optimal least-squares residual \"\min_x \norm{Ax - b}\". Thus, we have shown

  <\/span>   <\/span>\"\[\expect\norm{A\hat{x} - b}^2 = \left(1+\frac{d}{\ell-d-1}\right)\min_{x\in\real^d} \norm{Ax-b}^2.\]\"<\/p>Note that this is an exact formula<\/em> for the expected squared residual for the sketch-and-solve solution! Thus, the sketch-and-solve solution has an expected squared residual that factor \"1 + d/(\ell-d-1)\" larger than the optimal value. In particular,

  <\/span>   <\/span>\"\[\expect\norm{A\hat{x} - b}^2 = \left(1+\varepsilon\right)\min_{x\in\real^d} \norm{Ax-b}^2 \quad \text{when } \ell = \frac{d}{\varepsilon} + d + 1.\]\"<\/p><\/p>\n\n\n\n

\n

Remark (Existing literature):<\/em><\/strong> When I originally wrote this post, I had not seen these results anywhere in the literature. Thanks to Micha\u0142 Derezi\u0144ski<\/a>, who provided me with the following references: the following lecture notes<\/a> of Mert Pilanci<\/a>, equation 1 in this recent paper of Micha\u0142’s<\/a>, and this recent survey<\/a> by Micha\u0142 and Michael Mahoney<\/a>. I find it striking that these basic and beautiful results appear to only have been explicitly recorded very recently. Very big thanks also to Rob Webber<\/a> for providing help in preparing this post.<\/em><\/p>\n<\/blockquote>\n\n\n\n

\n
\n

Update<\/strong><\/em> (11\/21\/24): After this post was initially released, Mert Pilanci provided me with an earlier reference<\/a> (2020); see also this paper<\/a> for extensions.<\/em> He also mentions an even earlier paper<\/a> (2017) that does similar calculations in a statistical setting, but does not obtain exactly these formulas.<\/em> See also this paper<\/a> for exact and asymptomatically exact formulas for sketch-and-solve in the statistical setting.<\/em><\/p>\n<\/blockquote>\n<\/blockquote>\n","protected":false},"excerpt":{"rendered":"

In the comments to my post Does Sketching Work?, I was asked a very interesting question, which I will paraphrase as follows: Is the sketch-and-solve least-squares solution an unbiased estimate of the true least squares solution of ? In this post, I will answer this question for the special case in which is a GaussianRead 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":[9,12],"tags":[],"class_list":["post-1777","post","type-post","status-publish","format-standard","hentry","category-note-to-self","category-sketching"],"_links":{"self":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts\/1777","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=1777"}],"version-history":[{"count":14,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts\/1777\/revisions"}],"predecessor-version":[{"id":1951,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts\/1777\/revisions\/1951"}],"wp:attachment":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/media?parent=1777"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/categories?post=1777"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/tags?post=1777"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}