Pipeline-generated

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.

✓ 3 results · all verified · 0 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 3 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Sketched least squares and subspace embeddings — Examples

1 · Prerequisites

2 · Summary

The counterexample shows that embedding $Ran (A)$ alone does not give the stated residual guarantee. The next example computes the exact leverage scores of a maximally coherent design and compares leverage sampling with one uniform row sample. The final example computes a two-row isometric sketch for an overdetermined regression problem.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

CounterexampleConstruction: AI-generatedVerification: AI-generatedprecheck passOpen item page →

Embedding Ran(A) alone does not control the sketch-and-solve residual

Statement refuted

False claim: If $S$ is an $ε$ -subspace embedding for $Ran (A)$ , then every exact sketch least-squares minimizer $\hat{x}$ satisfies

∥ A \hat{x} - b ∥_{2}^{2} \leq \frac{1 + ε}{1 - ε} \min_{x} ∥ A x - b ∥_{2}^{2} .

Facts & Assumptions

Given: The claim above and the matrices in the Counterexample below.

[F1]

An $ε$ -embedding preserves every squared norm on its stated fixed subspace within factors $1 \pm ε$ (Oblivious squared-norm subspace embeddings).

[F2]

Sketch-and-solve minimizes $∥ S (A x - b) ∥_{2}$ on its exact converged branch (Rank-aware sketch-and-solve least squares).

Counterexample

1.1F1algebra

In $R^{2}$ , set $A = e_{1} = (1, 0)^{T}$ , $b = e_{1} + e_{2} = (1, 1)^{T}$ , and $S = (1 1)$ . For every $x \in R$ , $∥ S (A x) ∥_{2} = ∣ x ∣ = ∥ A x ∥_{2}$ , so [F1] holds on $Ran (A) = span (e_{1})$ with $ε = 1 / 4$ (indeed with zero distortion).

1.2F2algebra

The sketched residual is $S (A x - b) = x - 2$ , so its unique minimizer is $\hat{x} = 2$ by [F2]. The original squared residual is $∥ A x - b ∥_{2}^{2} = (x - 1)^{2} + 1$ , whose minimum is $1$ at $x_{*} = 1$ ; at $\hat{x} = 2$ it equals $2$ .

2.1step 1.1step 1.2algebra∎

At $ε = 1 / 4$ , the claimed factor is $(1 + ε) / (1 - ε) = 5 / 3$ , but $2 > 5 / 3 \cdot 1$ . Thus preserving $Ran (A)$ alone does not imply the residual guarantee; the lost direction is the component of $b$ orthogonal to $Ran (A)$ .

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passOpen item page →

Zero leverage rows and a maximally coherent one-dimensional design

Example

Take $Q = e_{1} = (1, 0, 0)^{T} \in R^{3 \times 1}$ . Compute its leverage scores and compare one exact leverage-proportional sample with one uniform row sample. Define the coherence here by $μ (U) = (n / d) \max_{i} ℓ_{i} (U)$ .

Facts & Assumptions

Given: The one-column orthonormal matrix $Q = e_{1}$ , the sampling procedure, and one sample with replacement.

[F1]

Leverage scores are row squared norms of an orthonormal basis and sum to the subspace dimension (Row leverage scores of a finite-dimensional subspace, Leverage scores are basis-independent and sum to the dimension).

[F2]

Sampling probability $π_{i}$ is allowed when $π_{i} \geq β ℓ_{i} / d$ ; a selected row is rescaled by $1 / \sqrt{m π_{i}}$ , with replacement (With-replacement leverage-score row sampling and rescaling).

[F3]

Embedding on a subspace means squared norms lie in $[1 - ε, 1 + ε]$ times their original values (Oblivious squared-norm subspace embeddings).

Verification

1.1F1algebra

The row norms of $Q$ give $(ℓ_{0}, ℓ_{1}, ℓ_{2}) = (1, 0, 0)$ , agreeing with the sum $d = 1$ in [F1]. Thus the last two rows have zero leverage and $μ (U) = (3 / 1) \cdot 1 = 3$ , the largest possible value since each leverage score is at most one.

2.1F2step 1.1algebra

With exact probabilities $π = (1, 0, 0)$ and one sample, [F2] selects row zero with probability one and returns $S = e_{1}^{T}$ . Then $S Q = 1$ , so the only unit vectors in $Ran (Q)$ retain squared norm exactly one. The zero-leverage rows are never sampled.

3.1F2F3step 2.1algebra∎

Uniform probabilities $π = (1 / 3, 1 / 3, 1 / 3)$ satisfy the lower bound in [F2] with $β = 1 / 3$ . With one sample, $S Q = \sqrt{3}$ if row zero is drawn, and $S Q = 0$ if row one or two is drawn. For $ε = 1 / 2$ , [F3] requires squared norm in $[1 / 2, 3 / 2]$ , which contains neither outcome; hence this one-row uniform sample fails with probability one, while the exact leverage sample in step 2.1 succeeds with probability one.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passOpen item page →

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$ .

Sketched least squares and subspace embeddings — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

Embedding Ran(A) alone does not control the sketch-and-solve residual

Statement refuted

Facts & Assumptions

Counterexample

Zero leverage rows and a maximally coherent one-dimensional design

Example

Facts & Assumptions

Verification

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

Example

Facts & Assumptions

Verification

Sources