Alphabeta Math
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.

Expected spectral error of the real Gaussian range finder

Statement

Assume Countable Choice for the finite-dimensional Gaussian probability measure. Let A∈Rm×n be fixed, k≥2, p≥2, ℓ=k+p≤min⁡(m,n), and draw Ω∈Rn×ℓ with iid standard real Gaussian entries. If Q is an orthonormal basis for Ran⁡(AΩ), then E∥A−QQ∗A∥2≤(1+kp−1)σk+1+ek+pp(∑j>kσj2)1/2. The rank of Q may be smaller than ℓ; exact arithmetic is assumed. The comparator σk+1 is the minimum spectral error among all rank-at-most-k approximations.

Facts & Assumptions

Given: The inherited Countable Choice assumption for the Gaussian law, and the fixed matrix, oversampling conditions, a standard real Gaussian draw, and the exact range-finder output.

[F1]

Orthogonal SVD coordinates split V∗Ω into independent standard Gaussian blocks (Orthogonal and unitary invariance of Gaussian matrix blocks).

[F2]

The k×ℓ block Ω1 has full row rank almost surely (A wide Gaussian matrix has full row rank almost surely).

[F3]

E∥Ω1†∥F2=k/(p−1) (Exact Frobenius moments of wide Gaussian pseudoinverses).

[F4]

E∥Ω1†∥2≤ek+p/p (Spectral moments and integrable tails for wide Gaussian pseudoinverses).

[F5]

For real Gaussian G, E∥SGT∥2≤∥S∥2∥T∥F+∥S∥F∥T∥2 (Real scaled-Gaussian spectral and Frobenius product bounds).

[F6]

The deterministic SVD partition gives ∥(I−QQ∗)A∥2≤σk+1+∥Σ2Ω2Ω1†∥2 when Ω1 has full row rank (Deterministic SVD-partition error bound for the range finder).

[F7]

Jensen's inequality gives (EX)2≤EX2 for nonnegative X with finite second moment (Jensen's inequality for expectation).

[F8]

The finite-dimensional expectation may be evaluated by iterated nonnegative integrals (Tonelli's theorem for nonnegative measurable functions on a sigma-finite product).

[F9]
[A1]

Countable Choice is used for the finite-dimensional Lebesgue Gaussian law (The Axiom of Countable Choice (ACω)).

[F10]

The finite scan returns a Borel orthogonal projector onto the sample range (Borel measurability and range correctness of the finite scan). Every orthonormal basis of that range gives the same projector: each projection has residual orthogonal to the range, so uniqueness of the orthogonal decomposition identifies them.

Proof

1.1givenF1F2F6F9F10A1choose

By [F9], σk+1 is the optimal rank-k comparator. Choose an SVD A=UΣV∗ and write V∗Ω=[Ω1T Ω2T]T with k top rows. By [F1] the blocks are independent standard Gaussian matrices; by [F2] and the wide-row-rank result Ω1 has full row rank almost surely. Thus [F6] gives ∥A−QQ∗A∥2≤σk+1+∥Σ2Ω2Ω1†∥2 off a null set. By [F10], every basis choice gives the same Borel projector as the finite scan. The error is therefore measurable and bounded by ∥A∥2 for every draw, so the exceptional null set does not change its expectation.

2.1step 1.1F1F3F4F5F8

Fix Ω1 and integrate first over the independent block Ω2. By [F5], EΩ2∥Σ2Ω2Ω1†∥2≤∥Σ2∥2∥Ω1†∥F+∥Σ2∥F∥Ω1†∥2. Tonelli [F8] and the finite moments [F3]–[F4] justify this iterated expectation.

3.1step 1.1step 2.1F3F4F7algebra∎

Take expectation over Ω1. By [F7] and [F3], E∥Ω1†∥F≤k/(p−1); [F4] supplies E∥Ω1†∥2≤ek+p/p. Since ∥Σ2∥2=σk+1 and ∥Σ2∥F=(∑j>kσj2)1/2, substituting into steps 1.1–2.1 gives the claimed bound.

Depends on

Used by

Dependency tree · two levels

60 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