Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Chen–Dongarra tail bound for ∥G†∥\|G^{\dagger}\|∥G†∥: P{∥G†∥>t}≤12π(k−r+1)(ekk−r+1)k−r+1t−(k−r+1)\mathbb P\{\|G^{\dagger}\|>t\}\le\frac{1}{\sqrt{2\pi(k-r+1)}}\bigl(\frac{e\sqrt k}{k-r+1}\bigr)^{k-r+1}t^{-(k-r+1)}P{∥G†∥>t}≤2π(k−r+1)​1​(k−r+1ek​​)k−r+1t−(k−r+1)

Open
GaussianMatrix.pinv_spectral_tail

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 with k≥r≥2k\ge r\ge2k≥r≥2, and let G†=GT(GGT)−1G^{\dagger}=G^{\mathsf T}(GG^{\mathsf T})^{-1}G†=GT(GGT)−1. For every t>0t>0t>0,

P{∥G†∥>t} ≤ 12π (k−r+1)(ekk−r+1)k−r+1t−(k−r+1).\mathbb P\bigl\{\|G^{\dagger}\|>t\bigr\}\ \le\ \frac{1}{\sqrt{2\pi\,(k-r+1)}}\left(\frac{e\sqrt{k}}{k-r+1}\right)^{k-r+1} t^{-(k-r+1)} .P{∥G†∥>t} ≤ 2π(k−r+1)​1​(k−r+1ek​​)k−r+1t−(k−r+1).

Since ∥G†∥=1/σmin⁡(G)\|G^{\dagger}\|=1/\sigma_{\min}(G)∥G†∥=1/σmin​(G), this is a small-ball estimate for the smallest singular value of a Gaussian matrix with polynomial decay of order k−r+1k-r+1k−r+1. It is the source of both the expected-norm bound E∥G†∥≤ek/(k−r)\mathbb E\|G^{\dagger}\|\le e\sqrt k/(k-r)E∥G†∥≤ek​/(k−r) and the large-deviation bound (10.6) for the spectral error of the randomized SVD. The exponent k−r+1k-r+1k−r+1 is sharp.

Formalization Note. The event is {t<∥G†∥}\{t<\|G^{\dagger}\|\}{t<∥G†∥} with pinvR as G†G^{\dagger}G†; real powers t−(k−r+1)t^{-(k-r+1)}t−(k−r+1) are Mathlib's rpow, with t>0t>0t>0. The bound is a real number converted to [0,∞][0,\infty][0,∞].

Preamble
import Definitions.Def_GaussianMatrix_basic

open MeasureTheory ProbabilityTheory
open scoped Matrix
Formal statement
namespace GaussianMatrix
theorem pinv_spectral_tail {r k : ℕ} (hr : 2 ≤ r) (hrk : r ≤ k) (t : ℝ) (ht : 0 < t) :
    (gaussianMatrix r k) {G | t < specNorm (pinvR (Matrix.of G))}
      ≤ ENNReal.ofReal ((1 / Real.sqrt (2 * Real.pi * ((k : ℝ) - r + 1)))
          * (Real.exp 1 * Real.sqrt k / ((k : ℝ) - r + 1)) ^ ((k : ℝ) - r + 1)
          * t ^ (-((k : ℝ) - r + 1))) := by sorry
end GaussianMatrix
Source
N. Halko, P.-G. Martinsson, J. A. Tropp, *Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions*, SIAM Review 53(2), 2011, https://arxiv.org/abs/0909.4061 (v2), Appendix A.2 p. 64, Proposition A.3 (from Chen–Dongarra, Lemma 4.1): for an m×nm\times nm×n standard Gaussian GGG with n≥m≥2n\ge m\ge2n≥m≥2 and t>0t>0t>0, P{∥G†∥>t}≤12π(n−m+1)(enn−m+1)n−m+1t−(n−m+1)\mathbb P\{\|G^\dagger\|>t\}\le\frac{1}{\sqrt{2\pi(n-m+1)}}\bigl(\frac{e\sqrt n}{n-m+1}\bigr)^{n-m+1}t^{-(n-m+1)}P{∥G†∥>t}≤2π(n−m+1)​1​(n−m+1en​​)n−m+1t−(n−m+1).
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. For an r×kr\times kr×k matrix GGG, write G†:=G⊤(GG⊤)−1G^{\dagger} := G^{\top}(GG^{\top})^{-1}G†:=G⊤(GG⊤)−1, a k×rk\times rk×r real matrix (the bundle's pinvR; it is the zero matrix when GG⊤GG^{\top}GG⊤ is singular), and let ∥A∥2\|A\|_2∥A∥2​ denote the bundle's specNorm, Mathlib's ℓ2→ℓ2\ell_2\to\ell_2ℓ2​→ℓ2​ operator norm (largest singular value).

Statement. Let r,kr,kr,k be natural numbers with 2≤r2\le r2≤r and r≤kr\le kr≤k, and let ttt be a real number with 0<t0<t0<t. Put m:=k−r+1m := k - r + 1m:=k−r+1 (computed in R\mathbb{R}R after casting; m≥1m\ge1m≥1). The theorem asserts the single inequality of extended non-negative reals

μr,k({ G  :  t<∥G⊤(GG⊤)−1∥2 })  ≤  ofReal⁡ ⁣(12π m⋅(e km)m⋅t−m),\mu_{r,k}\Big(\big\{\,G \;:\; t < \big\|G^{\top}(GG^{\top})^{-1}\big\|_{2}\,\big\}\Big)\;\le\;\operatorname{ofReal}\!\left(\frac{1}{\sqrt{2\pi\, m}}\cdot\left(\frac{e\,\sqrt{k}}{m}\right)^{m}\cdot t^{-m}\right),μr,k​({G:t<​G⊤(GG⊤)−1​2​})≤ofReal(2πm​1​⋅(mek​​)m⋅t−m),

where e=exp⁡(1)e=\exp(1)e=exp(1), ⋅\sqrt{\cdot}⋅​ is the real square root, the two powers (⋅)m(\cdot)^{m}(⋅)m and t−mt^{-m}t−m are real powers (real exponent m=k−r+1m = k-r+1m=k−r+1 and −m-m−m respectively), and ofReal⁡\operatorname{ofReal}ofReal sends a real number to [0,∞][0,\infty][0,∞] (negative inputs map to 000). The left-hand side is the outer measure μr,k\mu_{r,k}μr,k​ applied to the set of samples whose G†G^{\dagger}G† has spectral norm strictly greater than ttt.

Edge cases. Since k≥r≥2k\ge r\ge2k≥r≥2, we have k>0k>0k>0, m≥1m\ge1m≥1, and t>0t>0t>0, so the base ek/me\sqrt{k}/mek​/m is positive, t−m=1/tmt^{-m} = 1/t^{m}t−m=1/tm is an ordinary positive real, and the argument of ofReal⁡\operatorname{ofReal}ofReal is positive (no clipping at 000 occurs). The case k=rk=rk=r is allowed, giving m=1m=1m=1 and bound ofReal⁡(ek/(2π t))\operatorname{ofReal}\big(e\sqrt{k}/(\sqrt{2\pi}\,t)\big)ofReal(ek​/(2π​t)). Because μr,k\mu_{r,k}μr,k​ is a probability measure, the left side is at most 111, so the inequality is automatically true whenever the right side is ≥1\ge 1≥1 (e.g. for small ttt). Nothing is claimed for r∈{0,1}r\in\{0,1\}r∈{0,1} or for t≤0t\le 0t≤0. Samples with singular GG⊤GG^{\top}GG⊤ have ∥G†∥2=0\|G^{\dagger}\|_2=0∥G†∥2​=0 and are not in the set.

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