CounterexampleConstruction: 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.

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

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

3 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)