Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.1.1 — Matrix Gaussian and Rademacher series

Proved
TroppMatrixConcentration.ch4_matrix_series

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

matrix-concentrationrandom-matrices

Let BkB_kBk​ be a finite family of fixed complex m×nm\times nm×n matrices, with m,n≥1m,n\ge1m,n≥1. On an arbitrary probability space let gkg_kgk​ be independent measurable real random variables, either all standard normal or all Rademacher. Put Z=∑kgkBkZ=\sum_k g_k B_kZ=∑k​gk​Bk​ and define the actual second-moment statistic v=max⁡{∥EZZ∗∥,∥EZ∗Z∥}v=\max\{\|\mathbb E ZZ^*\|,\|\mathbb E Z^*Z\|\}v=max{∥EZZ∗∥,∥EZ∗Z∥}. Then

v=max⁡{∥∑kBkBk∗∥,∥∑kBk∗Bk∥},v=\max\left\{\left\|\sum_k B_kB_k^*\right\|,\left\|\sum_k B_k^*B_k\right\|\right\},v=max{​k∑​Bk​Bk∗​​,​k∑​Bk∗​Bk​​}, E∥Z∥≤2vlog⁡(m+n),\mathbb E\|Z\|\le\sqrt{2v\log(m+n)},E∥Z∥≤2vlog(m+n)​, P{∥Z∥≥t}≤(m+n)exp⁡(−t2/(2v))(t≥0).\mathbb P\{\|Z\|\ge t\}\le(m+n)\exp(-t^2/(2v))\qquad(t\ge0).P{∥Z∥≥t}≤(m+n)exp(−t2/(2v))(t≥0).

All norms are Euclidean operator norms. At v=0v=0v=0 the tail right side is m+nm+nm+n for t=0t=0t=0 and zero for t>0t>0t>0. The finite family may be empty. Both scalar distributions are included in the same theorem via a disjunction on the whole family's laws.

Preamble
import Definitions.Def_TroppMatrixConcentration_ch4_scalar_laws
import Definitions.Def_TroppMatrixConcentration_dilation

open MeasureTheory ProbabilityTheory
open scoped Matrix.Norms.L2Operator

Formal statement
namespace TroppMatrixConcentration

theorem ch4_matrix_series {Ω : Type*} [MeasurableSpace Ω]
    (μ : Measure Ω) [IsProbabilityMeasure μ] {m n N : ℕ} [NeZero m] [NeZero n]
    (B : Fin N → Matrix (Fin m) (Fin n) ℂ)
    (g : Fin N → Ω → ℝ) (hMeas : ∀ k, Measurable (g k))
    (hIndep : iIndepFun g μ)
    (hLaw : (∀ k, standardGaussianLaw μ (g k)) ∨ (∀ k, rademacherLaw μ (g k))) :
    let Z := fun ω => ∑ k, g k ω • B k
    let v := rectSecondMoment μ Z
    v = max (spectralNorm (∑ k, B k * (B k).conjTranspose))
      (spectralNorm (∑ k, (B k).conjTranspose * B k)) ∧
    (∫ ω, spectralNorm (Z ω) ∂μ) ≤ Real.sqrt (2 * v * Real.log (m + n)) ∧
    ∀ t : ℝ, 0 ≤ t → (μ {ω | t ≤ spectralNorm (Z ω)}).toReal ≤
      gaussianSeriesTail (m + n) v t := by sorry

end TroppMatrixConcentration
Source
Joel A. Tropp, An Introduction to Matrix Concentration Inequalities, arXiv:1501.01571v1 (7 January 2015); https://arxiv.org/abs/1501.01571v1; Theorem 4.1.1, equations (4.1.2–6), printed p. 42.
Read-back

What the Lean code literally says, in plain math · gpt-6

For every measurable space Ω\OmegaΩ, every probability measure μ\muμ on it, all positive natural numbers m,nm,nm,n, every natural number NNN (including N=0N=0N=0), every family of complex m×nm\times nm×n matrices (Bk)k=0N−1(B_k)_{k=0}^{N-1}(Bk​)k=0N−1​, and every family of measurable real-valued functions gk:Ω→Rg_k:\Omega\to\mathbb Rgk​:Ω→R that are jointly independent with respect to μ\muμ, suppose either that every pushforward measure (gk)∗μ(g_k)_*\mu(gk​)∗​μ is the real Gaussian distribution with mean 000 and variance 111, or that every (gk)∗μ(g_k)_*\mu(gk​)∗​μ equals 12δ1+12δ−1\tfrac12\delta_1+\tfrac12\delta_{-1}21​δ1​+21​δ−1​; this is a disjunction of two uniform choices for the whole family. Write A∗A^*A∗ for the conjugate transpose of a matrix AAA, and ∥A∥op\|A\|_{\mathrm{op}}∥A∥op​ for its operator norm between the complex Euclidean spaces of its column and row dimensions. Define Z(ω)=∑k=0N−1gk(ω)BkZ(\omega)=\sum_{k=0}^{N-1}g_k(\omega)B_kZ(ω)=∑k=0N−1​gk​(ω)Bk​, with multiplication by the real scalar acting on the complex matrix, and define v=max⁡{∥∫ΩZ(ω)Z(ω)∗ dμ(ω)∥op,∥∫ΩZ(ω)∗Z(ω) dμ(ω)∥op}v=\max\{\|\int_\Omega Z(\omega)Z(\omega)^*\,d\mu(\omega)\|_{\mathrm{op}},\|\int_\Omega Z(\omega)^*Z(\omega)\,d\mu(\omega)\|_{\mathrm{op}}\}v=max{∥∫Ω​Z(ω)Z(ω)∗dμ(ω)∥op​,∥∫Ω​Z(ω)∗Z(ω)dμ(ω)∥op​}, where these are Bochner integrals (using the convention that such an integral is zero when its integrand is not integrable). Then all three conclusions hold: v=max⁡{∥∑k=0N−1BkBk∗∥op,∥∑k=0N−1Bk∗Bk∥op}v=\max\{\|\sum_{k=0}^{N-1}B_kB_k^*\|_{\mathrm{op}},\|\sum_{k=0}^{N-1}B_k^*B_k\|_{\mathrm{op}}\}v=max{∥∑k=0N−1​Bk​Bk∗​∥op​,∥∑k=0N−1​Bk∗​Bk​∥op​}; ∫Ω∥Z(ω)∥op dμ(ω)≤2vlog⁡(m+n)\int_\Omega\|Z(\omega)\|_{\mathrm{op}}\,d\mu(\omega)\le\sqrt{2v\log(m+n)}∫Ω​∥Z(ω)∥op​dμ(ω)≤2vlog(m+n)​, with the natural logarithm and nonnegative real square root; and, for every real t≥0t\ge0t≥0, the real value of μ{ω:t≤∥Z(ω)∥op}\mu\{\omega:t\le\|Z(\omega)\|_{\mathrm{op}}\}μ{ω:t≤∥Z(ω)∥op​} is at most (m+n)exp⁡(−t2/(2v))(m+n)\exp(-t^2/(2v))(m+n)exp(−t2/(2v)) if v≠0v\ne0v=0, at most m+nm+nm+n if v=0v=0v=0 and t=0t=0t=0, and at most 000 if v=0v=0v=0 and t>0t>0t>0. The real value of the event measure is its extended-nonnegative-real-to-real conversion, which is the ordinary finite value here because μ\muμ is a probability measure. The tail event uses the non-strict inequality, so at t=0t=0t=0 it is all of Ω\OmegaΩ and the bound is 1≤m+n1\le m+n1≤m+n in either variance branch. If N=0N=0N=0, all family hypotheses are vacuous, all sums are empty, Z=0Z=0Z=0 and v=0v=0v=0, the expectation bound is 0≤00\le00≤0, and the stated zero-variance tail bounds apply; zero variance is also included for nonempty families. The assumptions exclude m=0m=0m=0 and n=0n=0n=0.

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

    Confirmed by the moderator at approval.

  • Endorsed by tc · Oct 7, 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