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 · 2 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 1 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Randomized low-rank approximation — Examples

1 · Prerequisites

2 · Summary

The examples show exact recovery of a rank- $k$ matrix almost surely, a slowly decaying diagonal spectrum for which the tail-Frobenius term can dominate the singular-value term, and a fully specified thresholded arithmetic model where powering loses a small mode unless QR is inserted between applications of $A$ and $A^{*}$ .

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

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

A small mode is lost by an unorthogonalized power pass

Example

Use the explicitly defined thresholded dyadic arithmetic that rounds any computed scalar of magnitude below $2^{- 70}$ to zero and computes all other operations exactly. For $A = diag (1, 2^{- 10})$ , $Ω = I_{2}$ , and power count $q = 4$ , the unorthogonalized product $(A A^{*})^{q} A Ω$ loses its second mode, while the deterministic QR iteration instructions from Reorthogonalized randomized power subspace iteration, executed with this supplied $Ω$ and the stated arithmetic, retain both coordinate modes. Here the Gaussian sampling step is omitted: this is a fixed-sketch arithmetic example, not a probabilistic claim or a general stability guarantee.

Facts & Assumptions

Given: The diagonal matrix, identity start block, power count, and the stated scalar rounding rule.

[F1]

After its sampling step, the power procedure inserts an orthonormal-basis computation after each application of $A^{*}$ and $A$ (Reorthogonalized randomized power subspace iteration).

Verification

1.1givenalgebra

Without intermediate QR, the second diagonal entry of $(A A^{*})^{q} A Ω$ is $(2^{- 10})^{2 q + 1} = 2^{- 90} < 2^{- 70}$ , whereas the leading entry is $1$ . The stated threshold therefore rounds the second column to zero, leaving rank $1$ .

2.1step 1.1F1givenalgebra∎

With QR after each multiplication, the first sample is $A Ω = diag (1, 2^{- 10})$ . Both columns are nonzero and orthogonal; because $2^{- 10} > 2^{- 70}$ , exact column normalization yields $Q_{0} = I_{2}$ . Each subsequent $A^{*} Q$ and $A \tilde{Q}$ is again $diag (1, 2^{- 10})$ , so the same QR step returns $I_{2}$ and neither mode is rounded away.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

Exact range recovery on a rank-k matrix

Example

Assume Countable Choice for the finite-dimensional Gaussian probability law. Let $A = diag (4, 1, 0, 0) \in R^{4 \times 4}$ , take target rank $k = 2$ , oversampling $p = 2$ , and draw $Ω \in R^{4 \times 4}$ with iid standard real Gaussian entries. The randomized range finder returns $Q Q^{*} A = A$ almost surely, so its spectral error is zero.

Facts & Assumptions

Given: Countable Choice for the finite Gaussian law, and the fixed diagonal matrix and the Gaussian range-finder draw.

[F1]

The algorithm returns an orthonormal basis of $Ran (A Ω)$ and then $Q Q^{*} A$ (Exact Gaussian randomized range finder).

[F2]

Orthogonal SVD coordinates preserve the iid Gaussian law (Orthogonal and unitary invariance of Gaussian matrix blocks).

[F3]

A wide Gaussian matrix has full row rank almost surely (A wide Gaussian matrix has full row rank almost surely).

Verification

1.1givenF2F3algebra

The displayed diagonal matrix has rank $2$ and SVD $A = U Σ V^{*}$ with $U = V = I$ and $Σ_{2} = 0$ . Write $Ω_{1}$ for its first two rows. By [F2]–[F3], $Ω_{1}$ has row rank $2$ almost surely.

2.1step 1.1F1givenalgebra∎

For every such draw, $A Ω = [\begin{array}{cc} 4 & 0 \\ 0 & 1 \\ 0 & 0 \\ 0 & 0 \end{array}] Ω_{1}$ has range exactly $span (e_{1}, e_{2})$ , since the first two rows of $Ω$ have rank $2$ and multiplication by $diag (4, 1)$ preserves rank. Thus $Q Q^{*}$ is the projector onto this span and $Q Q^{*} A = A$ .

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

A slowly decaying singular tail makes the Frobenius term dominate

Example

Fix integers $k \geq 2$ and $p \geq 2$ . For every $n \geq k + p$ , let $A_{n} = diag (1, 2^{- 1 / 2}, \dots, n^{- 1 / 2})$ . In the real Gaussian range-finder bound, the second term involving ${(\sum_{j > k} σ_{j}^{2})}^{1 / 2}$ eventually exceeds the term involving $σ_{k + 1}$ by an arbitrarily large factor as $n \to \infty$ .

Facts & Assumptions

Given: Fixed $k, p$ as above and the family of finite diagonal matrices $A_{n}$ .

[F1]

The expected error bound has first term $(1 + \sqrt{k / (p - 1)}) σ_{k + 1}$ and second term $(e \sqrt{k + p} / p) (\sum_{j > k} σ_{j}^{2})^{1 / 2}$ (Expected spectral error of the real Gaussian range finder).

Verification

1.1givenF1algebra

The diagonal entries are decreasing, so they are the singular values of $A_{n}$ , and $σ_{k + 1} = (k + 1)^{- 1 / 2}$ while $\sum_{j > k} σ_{j}^{2} = \sum_{j = k + 1}^{n} 1 / j$ .

2.1step 1.1algebra∎

Since $x \mapsto 1 / x$ is decreasing, $\sum_{j = k + 1}^{n} 1 / j \geq \int_{k + 1}^{n + 1} d x / x = \log ((n + 1) / (k + 1))$ , which diverges with $n$ . The coefficient $e \sqrt{k + p} / p$ is positive and fixed, while the first-term coefficient and $σ_{k + 1}$ are fixed. Therefore the ratio of the second term to the first tends to infinity; choosing $n$ large makes the tail-Frobenius contribution dominate by any prescribed factor.

Randomized low-rank approximation — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

A small mode is lost by an unorthogonalized power pass

Example

Facts & Assumptions

Verification

Exact range recovery on a rank-k matrix

Example

Facts & Assumptions

Verification

A slowly decaying singular tail makes the Frobenius term dominate

Example

Facts & Assumptions

Verification

Sources