{"id":2034,"date":"2025-02-12T02:09:19","date_gmt":"2025-02-12T02:09:19","guid":{"rendered":"https:\/\/www.ethanepperly.com\/?p=2034"},"modified":"2025-02-12T02:09:21","modified_gmt":"2025-02-12T02:09:21","slug":"note-to-self-how-accurate-is-sketch-and-solve","status":"publish","type":"post","link":"https:\/\/www.ethanepperly.com\/index.php\/2025\/02\/12\/note-to-self-how-accurate-is-sketch-and-solve\/","title":{"rendered":"Note to Self: How Accurate is Sketch and Solve?"},"content":{"rendered":"\n

Suppose we’re interested in solving an overdetermined linear least-squares problem<\/a>

(1) <\/span>   <\/span>\"\[x = \operatorname*{argmin}_{x \in \real^n} \norm{b-Ax}, \quad A \in \real^{m\times n}, \quad b \in \real^m. \]\"<\/p>Sketch-and-solve<\/a> is a popular method for getting a fast, approximate solution to (1). Let \"S \in \real^{d\times m}\" be a sketching matrix for \"\onebytwo{A}{b}\" of distortion \"\eta\" (see these previous<\/a> posts<\/a> of mine for a refresher on sketching if needed):

(2) <\/span>   <\/span>\"\[(1-\eta)\norm{y} \le \norm{Sy} \le (1+\eta)\norm{y} \quad \text{for every } y \in \operatorname{range}(\onebytwo{A}{b}). \]\"<\/p>The sketch-and-solve solution to (1) is given by

(3) <\/span>   <\/span>\"\[\hat{x} = \operatorname*{argmin}_{\hat{x}\in\real^n} \norm{Sb-(SA)\hat{x}}. \]\"<\/p><\/p>\n\n\n\n

How small is the residual \"\norm{b-A\hat{x}}\"of the sketch-and-solve solution? Here’s a one bound:<\/p>\n\n\n\n

\n

Proposition 1 (Sketch-and-solve, \"1+\order(\eta)\" bound).<\/strong> The sketch-and-solve solution (3) satisfies the bound

  <\/span>   <\/span>\"\[\norm{b-A\hat{x}} \le \frac{1+\eta}{1-\eta} \cdot \norm{b-Ax} = (1 + 2\eta + \order(\eta^2))\norm{b-Ax}.\]\"<\/p><\/p>\n<\/blockquote>\n\n\n\n

Let’s prove this bound. The residual \"b-A\hat{x}\" is in the range of \"\onebytwo{A}{b}\". Therefore, by (2),

  <\/span>   <\/span>\"\[(1-\eta) \norm{b-A\hat{x}} \le \norm{S(b-A\hat{x})}.\]\"<\/p>Rearranging gives

  <\/span>   <\/span>\"\[\norm{b-A\hat{x}} \le \frac{1}{1-\eta}\norm{S(b-A\hat{x})}.\]\"<\/p>By the optimality of the sketch-and-solve solution (3), \"\norm{S(b-A\hat{x})}\" is minimized for the value \"\hat{x}\". Thus, its value can only increase by replacing \"\hat{x}\" by \"x\":

  <\/span>   <\/span>\"\[\norm{b-A\hat{x}} \le \frac{1}{1-\eta}\norm{S(b-A\hat{x})}\le \frac{1}{1-\eta}\norm{S(b-Ax)}.\]\"<\/p>Invoke property (2) a final time to obtain

(4) <\/span>   <\/span>\"\[\norm{b-A\hat{x}} \le \frac{1}{1-\eta}\norm{S(b-A\hat{x})}\le \frac{1}{1-\eta}\norm{S(b-Ax)}\le \frac{1+\eta}{1-\eta}\cdot \norm{b-Ax}. \]\"<\/p>We’ve completed the proof of Proposition 1. In fact, were we to want to write the proof concisely, equation (4) represents a single-line proof of Proposition 1.<\/p>\n\n\n\n

The conclusion of Proposition 1 appears to be that the residual norm \"\norm{b-A\hat{x}}\" may be a factor \"1+\order(\eta^1)\" larger than the minimal least-squares residual \"\norm{b-Ax}\". Interestingly, this conclusion is not sharp. In fact, the residual for sketch-and-solve can only be at most \"1+\order(\eta^2)\" larger than optimal. This fact has been known at least since the work of Drineas, Mahoney, Muthukrishnan, and Sarl\u00f3s (2007)<\/a>. The note of Larsen and Kolda (2022)<\/a> provides a nice summary of Drineas et al.’s argument. My goal in this post is to simplify this argument even further, making it as elementary as possible.<\/p>\n\n\n\n

Notation<\/h2>\n\n\n\n

To make our lives easier, we’ll begin by defining some notation. Let

(5) <\/span>   <\/span>\"\[A = UC \quad \text{for } U\in\real^{m\times n}, \: B \in \real^{n\times n} \]\"<\/p>be any factorization of \"A\" into a matrix \"U\" with orthonormal columns and a square nonsingular matrix \"C\". Such a factorization can be computed using a QR<\/a> or polar<\/a> decomposition. Let

  <\/span>   <\/span>\"\[r = b-Ax\]\"<\/p>denote the optimal least-squares residual. We will have occasion to scale \"r\" so that it is a unit vector

  <\/span>   <\/span>\"\[\overline{r} = \frac{r}{\norm{r}}.\]\"<\/p>Note that the optimality condition for the least-squares problem (1) is that the residual \"r\" is orthogonal to \"\operatorname{range}(A)\". Consequently,

(6) <\/span>   <\/span>\"\[\onebytwo{U}{\overline{r}} \quad \text{is an orthonormal basis for } \operatorname{range}(\onebytwo{A}{b}). \]\"<\/p><\/p>\n\n\n\n

Sketching the basis<\/h2>\n\n\n\n

As saw in (6), the matrix \"\onebytwo{U}{\overline{r}}\" is an orthonormal basis for \"\operatorname{range}(\onebytwo{A}{b})\". To get a sharper analysis of sketch-and-solve, we will need the following result, which shows that \"S\onebytwo{U}{\overline{r}}\" is an “almost orthonormal basis”.<\/p>\n\n\n\n

Lemma 2 (Sketching the basis):<\/strong> The matrix \"S\onebytwo{U}{\overline{r}}\" has nearly orthonormal columns in the sense that

(7) <\/span>   <\/span>\"\[\sigma_{\rm min}(S\onebytwo{U}{\overline{r}}) \ge 1-\eta, \quad \sigma_{\rm max}(S\onebytwo{U}{\overline{r}}) \le 1+\eta. \]\"<\/p>Consequently,

(8) <\/span>   <\/span>\"\[\norm{\onebytwo{U}{\overline{r}}^\top S^\top S\onebytwo{U}{\overline{r}} - I} \le 2\eta+\eta^2. \]\"<\/p><\/p>\n\n\n\n

This result is a pretty direct reformulation of the sketching property (2). By the variational characterization of the minimum singular value, we have

  <\/span>   <\/span>\"\[\sigma_{\rm min}(S\onebytwo{U}{\overline{r}}) = \min_{\norm{z}=1} \norm{S\onebytwo{U}{\overline{r}}z}.\]\"<\/p>The vector \"\onebytwo{U}{\overline{r}}z\" is in the range of \"\onebytwo{A}{b}\". Thus, by (2),

  <\/span>   <\/span>\"\[\sigma_{\rm min}(S\onebytwo{U}{\overline{r}}) = \min_{\norm{z}=1} \norm{S\onebytwo{U}{\overline{r}}z} \ge (1-\eta) \min_{\norm{z}=1} \norm{\onebytwo{U}{\overline{r}}z} = 1-\eta.\]\"<\/p>For the last equality, we used the fact that \"\onebytwo{U}{\overline{r}}\" has orthonormal columns and thus

  <\/span>   <\/span>\"\[\norm{\onebytwo{U}{\overline{r}}z} = \norm{z} \quad \text{for every } z \in \real^{n+1}.\]\"<\/p>This proves the first inequality in (7). The second inequality follows along similar lines.<\/p>\n\n\n\n

For a tall matrix \"F\", the eigenvalues of \"F^\top F\" are equal to the squared singular values of \"F\". Applying this result to \"F = \onebytwo{U}{\overline{r}}\" gives

  <\/span>   <\/span>\"\[(1-\eta)^2 \le \lambda_{\rm min}(\onebytwo{U}{\overline{r}}^\top S^\top S\onebytwo{U}{\overline{r}}) \le \lambda_{\rm max}(\onebytwo{U}{\overline{r}}^\top S^\top S\onebytwo{U}{\overline{r}}) \le (1+\eta)^2.\]\"<\/p>Subtracting the identity matrix shifts all the eigenvalues down by \"1\":

  <\/span>   <\/span>\"\[-2\eta+\eta^2 \le \lambda_{\rm min}(\onebytwo{U}{\overline{r}}^\top S^\top S\onebytwo{U}{\overline{r}}-I) \le \lambda_{\rm max}(\onebytwo{U}{\overline{r}}^\top S^\top S\onebytwo{U}{\overline{r}}-I) \le 2\eta+\eta^2.\]\"<\/p>The spectral norm is equal to the largest eigenvalue in absolute value. Thus

  <\/span>   <\/span>\"\[\norm{\onebytwo{U}{\overline{r}}^\top S^\top S\onebytwo{U}{\overline{r}}-I} \le \max(2\eta+\eta^2,-(-2\eta+\eta^2)) = 2\eta+\eta^2.\]\"<\/p>This proves (8).<\/p>\n\n\n\n

Sketch-and-Solve: Better Analysis<\/h2>\n\n\n\n

With Lemma 2 in hand, we are ready to state and prove our main result:<\/p>\n\n\n\n

\n

Theorem 3 (Sketch-and-solve, \"1+\order(\eta^2)\" bound).<\/strong> The sketch-and-solve solution (3) satisfies the bound

(9) <\/span>   <\/span>\"\[\norm{b-A\hat{x}}^2 \le \left(1 + \frac{(2\eta+\eta^2)^2}{(1-\eta)^4}\right) \norm{b-Ax}^2 \le \left(1 + \frac{9\eta^2}{(1-\eta)^4}\right)\norm{b-Ax}^2. \]\"<\/p>As a consequence,

(10) <\/span>   <\/span>\"\[\norm{b-A\hat{x}}^2 \le (1+4\eta^2+\order(\eta^3)) \norm{b-Ax}^2 \]\"<\/p>and

(11) <\/span>   <\/span>\"\[\norm{b-A\hat{x}} \le (1+2\eta^2+\order(\eta^3)) \norm{b-Ax}. \]\"<\/p><\/p>\n<\/blockquote>\n\n\n\n

Let’s prove Theorem 3. Begin by decomposing the sketch-and-solve residual \"b - A\hat{x}\":

  <\/span>   <\/span>\"\[b - A\hat{x} = b - Ax + Ax - A\hat{x} = r + A(\hat{x}-x).\]\"<\/p>The residual \"r\" is orthogonal to the range of \"A\". Thus, by the Pythagorean theorem,

(12) <\/span>   <\/span>\"\[\norm{b-A\hat{x}}^2 = \norm{r}^2 + \norm{A(\hat{x}-x)}^2. \]\"<\/p><\/p>\n\n\n\n

To bound \"\norm{A(\hat{x}-x)}^2\", it will help us to have a more convenient formula for \"\hat{x}-x\". To this end, reparametrize the sketch-and-solve least-squares problem as an optimization problem over the error \"e \coloneqq \hat{x} - x\":

  <\/span>   <\/span>\"\[\hat{x} = \operatorname*{argmin}_{\hat{x}\in\real^n} \norm{S(b - Ax)-SA(\hat{x}-x)} \implies \hat{x} - x = \operatorname*{argmin}_{e\in\real^n} \norm{Sr - SAe}.\]\"<\/p>Applying the normal equations to this least-squares problem, we get

  <\/span>   <\/span>\"\[\hat{x} - x = (A^\top S^\top SA)^{-1} A^\top S^\top Sr.\]\"<\/p>Now, invoke the factorization (5):

  <\/span>   <\/span>\"\[\hat{x} - x = C^{-1} (U^\top S^\top SU)^{-1} U^\top S^\top Sr.\]\"<\/p>Thus,

  <\/span>   <\/span>\"\[A(\hat{x} - x) = U(U^\top S^\top SU)^{-1} U^\top S^\top Sr.\]\"<\/p>Taking norms and using the definition \"r = \norm{r} \cdot \overline{r}\", we obtain

(13) <\/span>   <\/span>\"\[\norm{A(\hat{x} - x)} \le \norm{(U^\top S^\top S U)^{-1}} \cdot \norm{U^\top S^\top S \overline{r}} \cdot \norm{r}. \]\"<\/p>
We now work to bound the two factors in (10). The matrix \"SU\" is a submatrix of \"S\onebytwo{U}{\overline{r}}\". Thus, by (7),

  <\/span>   <\/span>\"\[\sigma_{\rm min}(SU) \ge \sigma_{\rm min}(S\onebytwo{U}{\overline{r}}) \ge 1-\eta.\]\"<\/p>Consequently,

  <\/span>   <\/span>\"\[\norm{(U^\top S^\top S U)^{-1}} = \sigma_{\rm min}^2(SU) \le \frac{1}{(1-\eta)^2}.\]\"<\/p>The matrix \"U^\top S^\top S\overline{r}\" is a submatrix of \"\onebytwo{U}{\overline{r}}S^\top S\onebytwo{U}{\overline{r}} - I\". Thus, by (8),

  <\/span>   <\/span>\"\[\norm{U^\top S^\top S \overline{r}} \le \norm{\onebytwo{U}{\overline{r}}S^\top S\onebytwo{U}{\overline{r}} - I}\le 2\eta + \eta^2.\]\"<\/p>Substituting the two previous displays into (13) yields

  <\/span>   <\/span>\"\[\norm{A(\hat{x} - x)} \le \frac{2\eta+\eta^2}{(1-\eta)^2} \cdot \norm{r}.\]\"<\/p>Plugging this display into (12) proves (9). Equations (10) and (11) follow from (9) and a Taylor series expansion. This proves Theorem 3.<\/p>\n\n\n\n

Can We Do Better?<\/h2>\n\n\n\n

In the limit \"\eta \to 0\", Theorem 3 identifies the correct \"1+\order(\eta^2)\" scaling for sketch-and-solve, consistent both with numerical experiments, exact computations for Gaussian embeddings<\/a>, and lower bounds for solving least-squares problems by row subselection<\/a>. However, comparing results for Gaussian embeddings shows there may be room for improvement. Here is an informal statement of the Gaussian results:<\/p>\n\n\n\n

\n

Informal Theorem 4 (Gaussian sketch-and-solve):<\/strong> Appropriately scaled, a \"d\times m\" Gaussian matrix is an \"\eta\"-sketching matrix provided \"d\approx n/\eta^2\". The expected least-squares residual is

(14) <\/span>   <\/span>\"\[\expect \norm{b - A\hat{x}}^2 \approx \left(1 + \frac{\eta^2}{(1+\eta)(1-\eta)}\right) \norm{b - Ax}^2.\]\"<\/p><\/p>\n<\/blockquote>\n\n\n\n

See this post of mine<\/a> for a formal version of this result, its proof, and a discussion of the history of this result. We see that the bound (9) for general embeddings takes the form \"1 + \order((1-\eta)^{-4})\" in the limit \"\eta\to 1\", whereas the bound (14) for Gaussian embeddings scales like \"1 + \order((1-\eta)^{-1})\". We leave it as a conjecture\/open problem whether there is an improved argument for general subspace embeddings:<\/p>\n\n\n\n

\n

Conjecture 5 (Sketch-and-solve, large \"\eta\"):<\/strong> The sketch-and-solve solution (3) satisfies the bound

  <\/span>   <\/span>\"\[\norm{b-A\hat{x}}^2 \le \left(1 + \frac{C\eta^2}{1-\eta}\right)\norm{b-Ax}^2\]\"<\/p>for an absolute constant \"C > 0\".<\/p>\n<\/blockquote>\n\n\n\n

\n\n\n\n

Notes:<\/em><\/strong> For another proof demonstrating the correction \"\order(\eta^2)\" scaling for a different type of dimensionality reduction (leverage score sampling), check out this article<\/a> by Raphael Meyer<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"

Suppose we’re interested in solving an overdetermined linear least-squares problem (1)   Sketch-and-solve is a popular method for getting a fast, approximate solution to (1). Let be a sketching matrix for of distortion (see these previous posts of mine for a refresher on sketching if needed): (2)   The sketch-and-solve solution to (1) is givenRead 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-2034","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\/2034","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=2034"}],"version-history":[{"count":17,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts\/2034\/revisions"}],"predecessor-version":[{"id":2060,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts\/2034\/revisions\/2060"}],"wp:attachment":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/media?parent=2034"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/categories?post=2034"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/tags?post=2034"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}