The expected error of the randomized SVD with a Gaussian test matrix is times the optimal error (Halko–Martinsson–Tropp 2011, Theorem 10.5). The factor is for a standard Gaussian matrix : the quality of every Gaussian sketching method is governed by inverse moments of a Gaussian matrix — moments of its pseudoinverse, equivalently of the inverse of the Wishart matrix . The expected spectral error uses instead (Tropp–Webber 2023, Lemmas B.2–B.3), and deviation bounds use tail estimates for both norms (HMT Proposition 10.4). None of these inverse moments is available in Mathlib. This mission proves them.
A standard Gaussian matrix has independent entries; its law is . Throughout, is wide or square, , so that is almost surely invertible; is a Wishart matrix with degrees of freedom and is inverse-Wishart.
The pseudoinverse of a full-row-rank matrix is . Its norms are determined by the inverse Wishart matrix:
where is the Frobenius norm, the spectral norm (largest singular value) and the smallest of the singular values of . The letter denotes Euler's number.
For integer and ,
The case is , the spectral inverse moment at the heart of expected spectral-norm error bounds. It is the goal because it is the one inverse moment that is not an exact formula: its proof passes through Edelman's bound on the density of and an explicit integration, and it implies the expectation bound of HMT Proposition 10.2 by Jensen's inequality.
The results. Combined with the second-moment identity and block independence of Mission I, the Frobenius inverse moment gives the expected Frobenius error of the randomized SVD and of generalized Nyström; the spectral inverse moment gives the expected spectral error and the core-noise bounds of truncated sketching methods; the two tail bounds give the large-deviation statements of HMT §10.3. The second-order inverse-Wishart moments quantify the variance of , which Tropp–Webber use for concentration of the randomized SVD error.
Formalizing them. The inverse-Wishart mean and the second-order moments are classical multivariate-statistics formulas (Muirhead; von Rosen) with no Mathlib counterpart. The Chen–Dongarra tail requires the exact distribution of , or at least Edelman's density bound; the Frobenius tail is HMT's own argument through the bidiagonal (Householder) model of a Gaussian matrix and chi-square moment estimates. Every statement here is a proved theorem in the literature; none has a machine-checked proof.
There is no Wishart distribution in Mathlib. The direct approach — compute the density of and integrate — needs the Wishart density, a change of variables on the cone of positive-definite matrices, and the matrix-variate gamma function. The classical route to the mean avoids this: by rotational invariance has the same law as for every orthogonal , so its mean is a multiple of the identity, and the trace is -type quantities whose means are elementary; making "the diagonal entries of are reciprocals of variables" rigorous requires the Gram–Schmidt (QR) decomposition of a Gaussian matrix and the independence of its factors. The spectral inverse moment needs a lower-tail bound for of the exact order ; a union bound over rows loses a factor and does not give the stated constant. The naive attempt to bound by loses a factor as well.
is sampled from the product measure on arrays; is Mathlib's total matrix inverse, equal to on the null set where is singular, and is defined as (pinvR). Every inequality is stated together with integrability of its integrand, so the Lean convention that a non-integrable function integrates to cannot make a bound vacuous; identities with nonzero right-hand sides force integrability on their own but are also stated with it. The inverse-Wishart mean is stated entrywise. Tail bounds are inequalities between a measure in and of the real bound. Real powers with non-integer exponents are Mathlib's rpow; all bases are positive under the hypotheses. The spectral norm is Mathlib's operator norm. The sizes follow Tropp–Webber (); HMT's and conventions are translated in each item's source field.
Welcome contributions: a Wishart/inverse-Wishart library (QR decomposition of a Gaussian matrix, Bartlett decomposition, chi-square moments ), and the distribution of of a Gaussian matrix (Edelman).
Shared definitions: the items of this mission import Definitions.Def_GaussianMatrix_basic, a draft of Mission I; submit that proposal first so the import resolves at compile time.
Series: I. Rotation Invariance and Moment Identities · II. Inverse Moments of the Pseudoinverse · III. Extreme Singular Values and Concentration. All three missions share the definition bundle GaussianMatrix_basic, published with Mission I, and the namespace GaussianMatrix.
namespace GaussianMatrix
theorem inverse_wishart_spectral_moment {r k p : ℕ} (hp : 1 ≤ p) (hp18 : p ≤ 18)
(hrk : r + 2 * p ≤ k) :
Integrable (fun G : Fin r → Fin k → ℝ => specNorm (Matrix.of G * (Matrix.of G)ᵀ)⁻¹ ^ p)
(gaussianMatrix r k) ∧
∫ G, specNorm (Matrix.of G * (Matrix.of G)ᵀ)⁻¹ ^ p ∂(gaussianMatrix r k)
≤ (Real.exp 1 ^ 2 * ((k : ℝ) + r) / (2 * ((k : ℝ) - r) ^ 2)) ^ p := by sorry
end GaussianMatrixLet be a standard Gaussian matrix, let be an integer with , and assume . Then is integrable and
where is the spectral norm. Since , this bounds the -th inverse moment of the smallest singular value of a Gaussian matrix.
The case , , is the spectral-norm input for expected spectral-norm error bounds of the randomized SVD and of truncated sketching algorithms, where it is combined with the Frobenius inverse moment . The proof in the source starts from Edelman's bound on the density of .
Formalization Note. The bound is stated in the equivalent form , together with integrability of the integrand. The source writes the hypothesis as with the moment order (a typographical variant of ); its proof uses exactly .
No open leaves. Every sub-goal is proved or awaiting decomposition.