ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck pass

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

An exact two-row sketch for a three-row regression problem

Example

Let $A = (1, 1, 1)^{T}$ , $b = e_{1}$ , and let $S \in R^{2 \times 3}$ have rows $q_{1}^{T} = (1, 1, 1) / \sqrt{3}$ and $q_{2}^{T} = (2, - 1, - 1) / \sqrt{6}$ . Compute the original and sketched least-squares minimizers and residuals.

Facts & Assumptions

Given: The matrices above and an exact-arithmetic sketch-and-solve execution that converges.

[F1]

The sketch is an $ε$ -embedding for a subspace when it preserves every squared norm there within factors $1 \pm ε$ (Oblivious squared-norm subspace embeddings).

[F2]

A converged exact sketch-and-solve execution returns a minimizer of the sketched least-squares objective (A converged exact sketch-and-solve run returns a sketch minimizer).

[F3]

If the embedding subspace includes $Ran (A)$ and $b$ , the exact residual bound follows from Embedding span(A,b) gives the sketch-and-solve residual factor.

Verification

1.1F1algebra

Direct calculation gives $∥ q_{1} ∥_{2} = ∥ q_{2} ∥_{2} = 1$ and $q_{1}^{T} q_{2} = 0$ . Also $A = \sqrt{3} q_{1}$ and $b = (1 / \sqrt{3}) q_{1} + \sqrt{2 / 3} q_{2}$ , so $span (A, b) = span (q_{1}, q_{2})$ . The rows of $S$ form an orthonormal basis of this subspace; hence $S$ preserves its squared norms exactly and [F1] holds for every $0 < ε < 1$ .

1.2algebra

For real $x$ , $∥ A x - b ∥_{2}^{2} = (x - 1)^{2} + x^{2} + x^{2} = 3 (x - 1 / 3)^{2} + 2 / 3$ . Thus the original minimizer is $x_{*} = 1 / 3$ and its residual squared is $2 / 3$ .

1.3F2algebra

The sketch gives $S A = (\sqrt{3}, 0)^{T}$ and $S b = (1 / \sqrt{3}, \sqrt{2 / 3})^{T}$ . Therefore $∥ S A x - S b ∥_{2}^{2} = 3 (x - 1 / 3)^{2} + 2 / 3$ ; by [F2], $\hat{x} = 1 / 3$ , with sketched residual squared $2 / 3$ . Substitution into $A \hat{x} - b = (- 2 / 3, 1 / 3, 1 / 3)^{T}$ gives physical residual squared $2 / 3$ as well.

2.1F1F3step 1.1step 1.2step 1.3algebra∎

The fixed-subspace embedding hypothesis in [F3] is satisfied by step 1.1, and the computed minimizer in step 1.3 satisfies $∥ A \hat{x} - b ∥_{2}^{2} = 2 / 3 \leq ((1 + ε) / (1 - ε)) (2 / 3)$ for $0 < ε < 1$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

7 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

David P. Woodruff, Sketching as a Tool for Numerical Linear Algebra, §2.5, Theorem 21 (standard reference, not scraped)
Michael W. Mahoney, Randomized Algorithms for Matrices and Data, §4.2 (standard reference, not scraped)