Expected spectral norm of a pseudo-inverted Gaussian matrix:
OpenGaussianMatrix.pinv_spectral_expectationLet be a standard Gaussian matrix with and , and let . Then is integrable and
where is the spectral norm.
In Halko–Martinsson–Tropp's notation ( is ) the bound reads : it is the spectral inverse moment that, together with the Frobenius inverse moment, yields the expected spectral-norm error bound of the randomized SVD. Its proof integrates the Chen–Dongarra tail bound for .
Formalization Note. is pinvR ( on the null set where is singular). The conclusion is the conjunction of integrability and the bound.
import Definitions.Def_GaussianMatrix_basic open MeasureTheory ProbabilityTheory open scoped Matrix
namespace GaussianMatrix
theorem pinv_spectral_expectation {r k : ℕ} (hr : 2 ≤ r) (hrk : r + 1 ≤ k) :
Integrable (fun G : Fin r → Fin k → ℝ => specNorm (pinvR (Matrix.of G))) (gaussianMatrix r k) ∧
∫ G, specNorm (pinvR (Matrix.of G)) ∂(gaussianMatrix r k)
≤ Real.exp 1 * Real.sqrt k / ((k : ℝ) - r) := by sorry
end GaussianMatrixRead-back
What the Lean code literally says, in plain math · claude-fable-5-1
Throughout, denotes the measure called gaussianMatrix r k: the product measure on the function space in which every one of the coordinates is an independent standard normal ; it is a probability measure, and a sample is viewed as the real matrix with entries . Matrix inversion is Mathlib's total inverse on square real matrices: it is the usual inverse when the determinant is nonzero and is the zero matrix otherwise. For an matrix , write , a real matrix (the bundle's pinvR; it is the zero matrix when is singular). The bundle's specNorm of a matrix is Mathlib's operator norm , the largest singular value.
Statement. Let be natural numbers with and . The theorem asserts the conjunction of:
-
Integrability. The function is integrable with respect to .
-
Upper bound.
where , is the real square root of cast to , and by hypothesis, so the division is ordinary.
Edge cases. This is a one-sided inequality (). The hypothesis excludes and ; nothing is claimed for those. The hypothesis allows , in which case the bound is . The integral is Lean's real Bochner integral (which is for non-integrable integrands; part 1 asserts integrability). On the null set where is singular, and the integrand is .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.