Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Tropp–Webber inverse spectral moment: (E∥(GGT)−1∥p)1/p≤e2(k+r)2(k−r)2(\mathbb E\|(GG^{\mathsf T})^{-1}\|^p)^{1/p}\le\frac{e^2(k+r)}{2(k-r)^2}(E∥(GGT)−1∥p)1/p≤2(k−r)2e2(k+r)​ for 1≤p≤181\le p\le181≤p≤18, k≥r+2pk\ge r+2pk≥r+2p

Proved
GaussianMatrix.inverse_wishart_spectral_moment

by tc · Oct 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

gaussian-matrixprobabilityrandom-matrix-theoryrandomized-numerical-linear-algebra

Let G∈Rr×kG\in\mathbb R^{r\times k}G∈Rr×k be a standard Gaussian matrix, let ppp be an integer with 1≤p≤181\le p\le181≤p≤18, and assume k≥r+2pk\ge r+2pk≥r+2p. Then ∥(GGT)−1∥p\|(GG^{\mathsf T})^{-1}\|^p∥(GGT)−1∥p is integrable and

(E ∥(GGT)−1∥p)1/p ≤ e2 (k+r)2 (k−r)2,\Bigl(\mathbb E\,\bigl\|(GG^{\mathsf T})^{-1}\bigr\|^p\Bigr)^{1/p}\ \le\ \frac{e^2\,(k+r)}{2\,(k-r)^2},(E​(GGT)−1​p)1/p ≤ 2(k−r)2e2(k+r)​,

where ∥⋅∥\|\cdot\|∥⋅∥ is the spectral norm. Since ∥(GGT)−1∥=∥G†∥2=σmin⁡(G)−2\|(GG^{\mathsf T})^{-1}\|=\|G^{\dagger}\|^2=\sigma_{\min}(G)^{-2}∥(GGT)−1∥=∥G†∥2=σmin​(G)−2, this bounds the 2p2p2p-th inverse moment of the smallest singular value of a Gaussian matrix.

The case p=1p=1p=1, E∥G†∥2≤e2(k+r)/(2(k−r)2)\mathbb E\|G^{\dagger}\|^2\le e^2(k+r)/(2(k-r)^2)E∥G†∥2≤e2(k+r)/(2(k−r)2), 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 E∥G†∥F2=r/(k−r−1)\mathbb E\|G^{\dagger}\|_F^2=r/(k-r-1)E∥G†∥F2​=r/(k−r−1). The proof in the source starts from Edelman's bound on the density of λmin⁡(GGT)\lambda_{\min}(GG^{\mathsf T})λmin​(GGT).

Formalization Note. The bound is stated in the equivalent form E∥(GGT)−1∥p≤(e2(k+r)/(2(k−r)2))p\mathbb E\|(GG^{\mathsf T})^{-1}\|^p\le\bigl(e^2(k+r)/(2(k-r)^2)\bigr)^pE∥(GGT)−1∥p≤(e2(k+r)/(2(k−r)2))p, together with integrability of the integrand. The source writes the hypothesis as k≥r+2mk\ge r+2mk≥r+2m with mmm the moment order (a typographical variant of ppp); its proof uses exactly k−r≥2pk-r\ge2pk−r≥2p.

Preamble
import Definitions.Def_GaussianMatrix_basic

open MeasureTheory ProbabilityTheory
open scoped Matrix
Formal statement
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 GaussianMatrix
Source
J. A. Tropp, R. J. Webber, *Randomized algorithms for low-rank matrix approximation: design, analysis, and applications*, 2023, https://arxiv.org/abs/2306.12418 (v1), Appendix B p. 52, Lemma B.3 (Inverse moment bounds, spectral norm), eq. (B.4): for 0≤p≤180\le p\le180≤p≤18 and k≥r+2pk\ge r+2pk≥r+2p (printed as r+2mr+2mr+2m), (E∥(GG∗)−1∥p)1/p≤e2(k+r)2(k−r)2(\mathbb E\|(GG^*)^{-1}\|^p)^{1/p}\le\frac{e^2(k+r)}{2(k-r)^2}(E∥(GG∗)−1∥p)1/p≤2(k−r)2e2(k+r)​; the proof's condition (B.8) is x=k−r≥2px=k-r\ge2px=k−r≥2p.
Read-back

What the Lean code literally says, in plain math · claude-fable-5-1

Throughout, μr,k\mu_{r,k}μr,k​ denotes the measure called gaussianMatrix r k: the product measure on the function space {0,…,r−1}×{0,…,k−1}→R\{0,\dots,r-1\}\times\{0,\dots,k-1\}\to\mathbb{R}{0,…,r−1}×{0,…,k−1}→R in which every one of the rkrkrk coordinates is an independent standard normal N(0,1)\mathcal N(0,1)N(0,1); it is a probability measure, and a sample GGG is viewed as the real r×kr\times kr×k matrix with entries GijG_{ij}Gij​. Matrix inversion (⋅)−1(\cdot)^{-1}(⋅)−1 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. The bundle's specNorm of a real matrix AAA is Mathlib's ℓ2→ℓ2\ell_2\to\ell_2ℓ2​→ℓ2​ operator norm

∥A∥2  =  sup⁡∥x∥2≤1∥Ax∥2,\|A\|_{2} \;=\; \sup_{\|x\|_2\le 1}\|Ax\|_2,∥A∥2​=∥x∥2​≤1sup​∥Ax∥2​,

i.e. the largest singular value of AAA (equal to 000 for the zero matrix and for any matrix with an empty index set).

Statement. Let r,k,pr,k,pr,k,p be natural numbers with 1≤p1\le p1≤p, p≤18p\le 18p≤18, and r+2p≤kr + 2p \le kr+2p≤k. Let W=GG⊤W = GG^{\top}W=GG⊤ be the r×rr\times rr×r Gram matrix of a sample GGG. The theorem asserts the conjunction of:

  1. Integrability. The function G↦∥(GG⊤)−1∥2 pG\mapsto \big\|(GG^{\top})^{-1}\big\|_{2}^{\,p}G↦​(GG⊤)−1​2p​ (natural-number power ppp of the spectral norm of the inverse Gram matrix) is integrable with respect to μr,k\mu_{r,k}μr,k​.

  2. Upper bound.

∫∥(GG⊤)−1∥2 p  dμr,k(G)  ≤  (e2 (k+r)2 (k−r)2)p,\int \big\|(GG^{\top})^{-1}\big\|_{2}^{\,p}\;d\mu_{r,k}(G)\;\le\;\left(\frac{e^{2}\,(k+r)}{2\,(k-r)^{2}}\right)^{p},∫​(GG⊤)−1​2p​dμr,k​(G)≤(2(k−r)2e2(k+r)​)p,

where e=exp⁡(1)e = \exp(1)e=exp(1), r,kr,kr,k are cast to R\mathbb{R}R, and the powers are natural-number powers. Under k≥r+2p≥r+2k\ge r+2p\ge r+2k≥r+2p≥r+2, (k−r)2≥4>0(k-r)^2\ge 4>0(k−r)2≥4>0, so the division is ordinary.

Edge cases. This is a one-sided inequality (≤\le≤), not an equality. The upper bound p≤18p\le 18p≤18 is an explicit hypothesis: nothing is claimed for p≥19p\ge 19p≥19, and nothing is claimed for p=0p=0p=0. The integral is Lean's real Bochner integral (which is 000 for non-integrable integrands; part 1 asserts integrability). On the null set where GG⊤GG^{\top}GG⊤ is singular, (GG⊤)−1=0(GG^{\top})^{-1}=0(GG⊤)−1=0 and the integrand is 000. When r=0r=0r=0, (GG⊤)−1(GG^{\top})^{-1}(GG⊤)−1 is the 0×00\times 00×0 matrix, its spectral norm is 000, so the left side is 0p=00^{p}=00p=0 (as p≥1p\ge1p≥1) and the right side is (e2/(2k))p>0\big(e^{2}/(2k)\big)^{p}>0(e2/(2k))p>0; the hypothesis then reads 2p≤k2p\le k2p≤k.

Human review
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by tc · Oct 9, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me