Gaussian approximate matrix multiplication:
ProvedGaussianMatrix.approx_multiplicationFix matrices and , let , and let have independent entries, i.e. with standard Gaussian. Then
The random product is the sketched (Monte Carlo) estimate of obtained from Gaussian test vectors; the identity gives its exact mean-squared error, decaying like . It is the second-moment input for one-pass low-rank approximation algorithms, where it controls the term with .
Formalization Note. is written as with standard Gaussian, so the hypothesis is exactly that the entries of are . The statement is the conjunction of the identity and the stated upper bound; the latter is the elementary inequality .
import Definitions.Def_GaussianMatrix_basic open MeasureTheory ProbabilityTheory open scoped Matrix
namespace GaussianMatrix
theorem approx_multiplication {a b n t : ℕ} (ht : 1 ≤ t) (M : Matrix (Fin a) (Fin n) ℝ)
(N : Matrix (Fin b) (Fin n) ℝ) :
∫ Ω, frobSq (M * ((1 / (t : ℝ)) • (Matrix.of Ω * (Matrix.of Ω)ᵀ)) * Nᵀ - M * Nᵀ)
∂(gaussianMatrix n t)
= (frobSq M * frobSq N + frobSq (M * Nᵀ)) / t ∧
(frobSq M * frobSq N + frobSq (M * Nᵀ)) / t ≤ 2 / t * (frobSq M * frobSq N) := by sorry
end GaussianMatrixRead-back
What the Lean code literally says, in plain math · claude-fable-5-1
Let be natural numbers (implicit) with the hypothesis (so ), and let and be arbitrary real matrices. Let be the law of an array with independent entries, and write (empty sum ). The statement is the conjunction of two claims. First,
where , the scalar is the real number (real division; since this is not the convention), , and the right-hand side divides by the real number . The left-hand side is Lean's Bochner integral, which by convention equals if the integrand (a degree-4 polynomial in the entries of ) is not integrable; integrability is not separately asserted. Second, the purely deterministic inequality
which involves no measure. Edge cases: , or may be ; if or every Frobenius quantity involving or respectively is and both sides of both claims reduce to ; if then , , are empty, all products are zero matrices, and both sides are .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.