LemmaStatement: AI-adaptedProof: AI-generatedPipeline-generatedjudge 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.

Measurability of the reorthogonalized power range finder

Statement

Assume Countable Choice. For fixed $A \in F^{m \times n}$ , sketch width $ℓ \geq 1$ , and integer $q \geq 0$ , the basis returned by Reorthogonalized randomized power subspace iteration is Borel measurable on each output-rank stratum. Its projector and spectral error on $A$ are Borel functions of $Ω$ , including rank-deficient and zero samples.

Facts & Assumptions

Given: Countable Choice, fixed $A$ , and finite integers $ℓ \geq 1$ , $q \geq 0$ .

[F1]

The power procedure applies the finite scan to $A Ω$ and then successively to $A^{*} Q_{j - 1}$ and $A {\tilde{Q}}_{j}$ , for $1 \leq j \leq q$ . Reorthogonalized randomized power subspace iteration

[F2]

The finite scan terminates, returns a basis of its input range, and is Borel on its finitely many output-rank strata; its projector and spectral error are Borel. Borel measurability and range correctness of the finite scan

[F3]

A composition of measurable maps is measurable (Composition with a Borel measurable outer map preserves measurability).

Proof

1.1givenF1F2F3algebra

By [F2], the initial scan on $A Ω$ is Borel, since multiplication by fixed $A$ is continuous. On each rank stratum, multiplication by fixed $A^{*}$ and then the scan are Borel by [F3], as are multiplication by $A$ and the next scan. There are finitely many possible ranks, so the resulting maps on their disjoint union are Borel. Finite induction over the $q$ iterations proves measurability of the final basis. The empty-basis branches remain empty under multiplication and scanning, and $q = 0$ is the initial scan.

2.1step 1.1F2algebra∎

On every rank stratum $Q \mapsto Q Q^{*}$ is continuous, and the matrix norm is continuous by the norm inequality in [F2]'s proof. Hence the final projector and error are Borel on their finite union, including zero samples.

Depends on

Used by

Cited to discharge well-definedness by Reorthogonalized randomized power subspace iteration.

Dependency tree · two levels

15 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

Halko, Martinsson, and Tropp, Finding Structure with Randomness, Algorithms 4.1 and 4.4 and Gaussian conventions in section 10.1; local prerequisite proof (standard reference, not scraped)