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 be fixed, , , , and draw with iid standard real Gaussian entries. If is an orthonormal basis for , then The rank of may be smaller than ; exact arithmetic is assumed. The comparator is the minimum spectral error among all rank-at-most- 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.
Orthogonal SVD coordinates split into independent standard Gaussian blocks (Orthogonal and unitary invariance of Gaussian matrix blocks).
The block has full row rank almost surely (A wide Gaussian matrix has full row rank almost surely).
For real Gaussian , (Real scaled-Gaussian spectral and Frobenius product bounds).
The deterministic SVD partition gives when has full row rank (Deterministic SVD-partition error bound for the range finder).
Jensen's inequality gives for nonnegative with finite second moment (Jensen's inequality for expectation).
The finite-dimensional expectation may be evaluated by iterated nonnegative integrals (Tonelli's theorem for nonnegative measurable functions on a sigma-finite product).
The best rank-at-most- spectral approximation error is (The best rank-at-most-k approximation in operator norm is the rank-k truncation of a singular value decomposition).
Countable Choice is used for the finite-dimensional Lebesgue Gaussian law (The Axiom of Countable Choice ()).
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
By [F9], is the optimal rank- comparator. Choose an SVD and write with top rows. By [F1] the blocks are independent standard Gaussian matrices; by [F2] and the wide-row-rank result has full row rank almost surely. Thus [F6] gives 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 for every draw, so the exceptional null set does not change its expectation.
Fix and integrate first over the independent block . By [F5], . Tonelli [F8] and the finite moments [F3]–[F4] justify this iterated expectation.
Take expectation over . By [F7] and [F3], ; [F4] supplies . Since and , substituting into steps 1.1–2.1 gives the claimed bound.
Depends on
- Exact Gaussian randomized range finder
- Orthogonal and unitary invariance of Gaussian matrix blocks
- A wide Gaussian matrix has full row rank almost surely
- Exact Frobenius moments of wide Gaussian pseudoinverses
- Spectral moments and integrable tails for wide Gaussian pseudoinverses
- Real scaled-Gaussian spectral and Frobenius product bounds
- Deterministic SVD-partition error bound for the range finder
- Every linear map between finite-dimensional real or complex inner product spaces admits a singular value decomposition
- The best rank-at-most-k approximation in operator norm is the rank-k truncation of a singular value decomposition
- The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||
- The operator norm is 0 on the zero domain and otherwise equals the largest singular value, attained at a right-singular vector
- Tonelli's theorem for nonnegative measurable functions on a sigma-finite product
- Jensen's inequality for expectation
- The Axiom of Countable Choice ($\mathrm{AC}_\omega$)
- Borel measurability and range correctness of the finite scan
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
- Halko, Martinsson, and Tropp, Finding Structure with Randomness, Theorem 10.6 and its proof (standard reference, not scraped)
- Martinsson and Tropp, Randomized Numerical Linear Algebra: Foundations & Algorithms, Theorem 11.5 (standard reference, not scraped)