TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

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.

A converged exact sketch-and-solve run returns a sketch minimizer

Statement

Let $C = S A$ and $c = S b$ be the sketch matrix and response in Rank-aware sketch-and-solve least squares. In exact arithmetic, if its zero- threshold SVD call converges and supplies an exact SVD record, the returned $\hat{x}$ is the unique minimum-Euclidean-norm minimizer of $∥ S A x - S b ∥_{2}$ , and the reported rank is $rank (S A)$ . No conclusion is asserted on an inconclusive or finite-precision unverified branch.

Facts & Assumptions

Given: Finite matrices $A, S$ , a vector $b$ , and an exact-arithmetic converged execution of the SVD call in the algorithm.

[F1]

The algorithm forms $C = S A$ , $c = S b$ and calls the SVD least-squares procedure at strict threshold $τ = 0$ ; only exact convergence with an exact SVD record is the branch under consideration (Rank-aware sketch-and-solve least squares).

[F2]

On exact convergence, the SVD threshold solver returns the unique minimum-norm least-squares vector for its truncated model; when every discarded singular value is zero, that is also the solution for the original matrix (The SVD threshold solver gives the unique minimum-norm fit to its truncated model).

Proof

Given: The hypotheses in the Statement.

1.1F1construct

Set $C = S A$ and $c = S b$ . By [F1], the converged call uses threshold zero and returns $\hat{x} = C_{0}^{+} c$ , where $C_{0}$ retains exactly the singular values of $C$ that are strictly positive.

2.1step 1.1algebra

In an exact SVD $C = U Σ V^{*}$ , zero singular values contribute zero terms and every positive singular value is retained at threshold zero. Thus $C_{0} = U Σ V^{*} = C$ , including the rank-zero case.

3.1F2step 2.1algebra∎

Apply [F2] to the truncated matrix $C_{0}$ . It says that $C_{0}^{+} c$ is its unique minimum-norm least-squares solution. By step 2.1, $C_{0} = C$ , so $\hat{x}$ is the unique minimum-norm minimizer of $∥ C x - c ∥_{2} = ∥ S A x - S b ∥_{2}$ ; the zero-threshold rank count is precisely the number of positive singular values of $C$ , hence $rank (C)$ .

Depends on

Used by

Dependency tree · two levels

13 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

Wen-Wei Lin, Lecture Notes of Matrix Computations, §3.2.2 (standard reference, not scraped)
David P. Woodruff, Sketching as a Tool for Numerical Linear Algebra, §2.5 (standard reference, not scraped)