TheoremStatement: AI-adaptedProof: AI-adaptedPipeline-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.

Power-rangefinder error transfer under finite expected powered error

Statement

Let $F \in {R, C}$ , let $(Ξ, A, P)$ be a probability space, let $A \in F^{m \times n}$ be fixed, let $ℓ \geq 1$ be an integer, and let $q \geq 0$ be an integer. Let $Ω : Ξ \to F^{n \times ℓ}$ be measurable and let $P : Ξ \to F^{m \times m}$ be a measurable orthogonal projector-valued map whose value $P (ξ)$ projects onto $Ran ((A A^{*})^{q} A Ω (ξ))$ . For Gaussian sketches this is the output range of Reorthogonalized randomized power subspace iteration. Assume $E ∥ (I - P) (A A^{*})^{q} A ∥_{2} < \infty,$ where expectation is with respect to $P$ . Then $E ∥ (I - P) A ∥_{2} \leq {(E ∥ (I - P) (A A^{*})^{q} A ∥_{2})}^{1 / (2 q + 1)} .$ This is a transfer inequality; it assumes the powered error expectation has already been bounded.

Facts & Assumptions

Given: A fixed finite matrix, a random test matrix, an integer $q \geq 0$ , and a finite expected powered error.

[F1]

The reorthogonalized procedure applies the finite scan to $A Ω$ , then to $A^{*} Q_{j - 1}$ and $A {\tilde{Q}}_{j}$ at each iteration (Reorthogonalized randomized power subspace iteration).

[F2]

For each orthogonal projector $P$ , $∥ (I - P) A ∥_{2} \leq ∥ (I - P) (A A^{*})^{q} A ∥_{2}^{1 / (2 q + 1)}$ (Orthogonal-projector power error inequality).

[F3]

Jensen's inequality applies to an integrable real random variable when its convex image is integrable or nonnegative (Jensen's inequality for expectation).

Proof

1.1givenF1algebra

For a Gaussian draw, write $S_{0} = Ran (A Ω)$ . At iteration $j$ of [F1], the intermediate range is $A^{*} S_{j - 1}$ and the next range is $A A^{*} S_{j - 1}$ , since replacing a matrix by a basis preserves its range. Induction gives $S_{q} = Ran ((A A^{*})^{q} A Ω)$ , including empty ranges and $q = 0$ . Thus the range specified directly in the statement agrees with the algorithm's output range for Gaussian draws. For a general measurable sketch, the statement specifies $P$ directly and requires no Gaussian sampling step.

2.1step 1.1F2F3algebra∎

Set $Z = ∥ (I - P) (A A^{*})^{q} A ∥_{2}$ . By [F2], $∥ (I - P) A ∥_{2} \leq Z^{1 / (2 q + 1)}$ pointwise. Since $Z$ is integrable and $Z^{1 / (2 q + 1)} \leq 1 + Z$ , Jensen [F3] applied to the convex function $- t^{1 / (2 q + 1)}$ gives $E Z^{1 / (2 q + 1)} \leq (E Z)^{1 / (2 q + 1)}$ . Taking expectations of the pointwise inequality proves the result.

Depends on

Used by

Dependency tree · two levels

12 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, Theorem 9.2 (standard reference, not scraped)
Martinsson and Tropp, Lemma 11.8 (standard reference, not scraped)