Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5.4.1 — Matrix Chernoff mgf and cgf bounds

Proved
TroppMatrixConcentration.ch5_chernoff_mgf_cgf

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

matrix-concentrationrandom-matrices

Let XXX be a measurable random complex d×dd\times dd×d matrix on a probability space, d≥1d\ge1d≥1, Hermitian almost surely. Assume 0≤λmin⁡(X)0\le\lambda_{\min}(X)0≤λmin​(X) and λmax⁡(X)≤L\lambda_{\max}(X)\le Lλmax​(X)≤L almost surely, for a common L≥0L\ge0L≥0. For every real θ\thetaθ, put c=(eθL−1)/Lc=(e^{\theta L}-1)/Lc=(eθL−1)/L when L>0L>0L>0, and c=θc=\thetac=θ when L=0L=0L=0. Then

EeθX⪯exp⁡(cEX),log⁡EeθX⪯cEX.\mathbb E e^{\theta X}\preceq\exp(c\mathbb EX),\qquad\log\mathbb E e^{\theta X}\preceq c\mathbb EX.EeθX⪯exp(cEX),logEeθX⪯cEX.

All expectations are Bochner integrals; boundedness supplies integrability. Both signs of θ\thetaθ, as well as θ=0\theta=0θ=0, are included. At L=0L=0L=0 the matrix XXX vanishes almost surely and the displayed relations have their deterministic interpretation.

Preamble
import Definitions.Def_TroppMatrixConcentration_ch5_chernoff_functions

open MeasureTheory ProbabilityTheory
open scoped Matrix.Norms.L2Operator

Formal statement
namespace TroppMatrixConcentration

theorem ch5_chernoff_mgf_cgf {Ω : Type*} [MeasurableSpace Ω]
    (μ : Measure Ω) [IsProbabilityMeasure μ] {d : ℕ} [NeZero d]
    (X : Ω → Matrix (Fin d) (Fin d) ℂ) (L : ℝ) (hL : 0 ≤ L)
    (hMeas : Measurable X) (hHerm : ∀ᵐ ω ∂μ, (X ω).IsHermitian)
    (hBound : ∀ᵐ ω ∂μ, 0 ≤ lambdaMin (X ω) ∧ lambdaMax (X ω) ≤ L)
    (θ : ℝ) :
    loewnerLE (∫ ω, matrixExp (θ • X ω) ∂μ)
      (matrixExp (chernoffCgfCoefficient L θ • (∫ ω, X ω ∂μ))) ∧
    loewnerLE (matrixLog (∫ ω, matrixExp (θ • X ω) ∂μ))
      (chernoffCgfCoefficient L θ • (∫ ω, X ω ∂μ)) := 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; Lemma 5.4.1, printed p. 70.
Read-back

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

For every measurable space Ω\OmegaΩ, every probability measure μ\muμ on it, every positive integer ddd (so d=0d=0d=0 is excluded), every Borel-measurable function X:Ω→Cd×dX:\Omega\to\mathbb C^{d\times d}X:Ω→Cd×d with rows and columns indexed by {0,…,d−1}\{0,\ldots,d-1\}{0,…,d−1}, and every real L≥0L\ge0L≥0, suppose that X(ω)X(\omega)X(ω) is Hermitian for μ\muμ-almost every ω\omegaω and that 0≤inf⁡σR(X(ω))0\le\inf\sigma_{\mathbb R}(X(\omega))0≤infσR​(X(ω)) and sup⁡σR(X(ω))≤L\sup\sigma_{\mathbb R}(X(\omega))\le LsupσR​(X(ω))≤L for μ\muμ-almost every ω\omegaω, where σR(A)\sigma_{\mathbb R}(A)σR​(A) denotes the spectrum of AAA as an element of the real matrix algebra (on Hermitian matrices these extrema are the smallest and largest eigenvalues). Then, for every real θ\thetaθ, including zero and negative values, set M=∫ΩX(ω) dμ(ω)M=\int_\Omega X(\omega)\,d\mu(\omega)M=∫Ω​X(ω)dμ(ω), Hθ=∫Ωexp⁡(θX(ω)) dμ(ω)H_\theta=\int_\Omega \exp(\theta X(\omega))\,d\mu(\omega)Hθ​=∫Ω​exp(θX(ω))dμ(ω), and cL(θ)=θc_L(\theta)=\thetacL​(θ)=θ if L=0L=0L=0, and cL(θ)=(eθL−1)/Lc_L(\theta)=(e^{\theta L}-1)/LcL​(θ)=(eθL−1)/L otherwise; both exp⁡(cL(θ)M)−Hθ\exp(c_L(\theta)M)-H_\thetaexp(cL​(θ)M)−Hθ​ and cL(θ)M−log⁡cfc(Hθ)c_L(\theta)M-\log_{\mathrm{cfc}}(H_\theta)cL​(θ)M−logcfc​(Hθ​) are positive semidefinite, meaning that each is Hermitian and has nonnegative quadratic form on every vector in Cd\mathbb C^dCd. Here the integrals are matrix-valued Bochner integrals, exp⁡(A)\exp(A)exp(A) is the normed-algebra exponential, scalar multiplication is by real scalars, and log⁡cfc(A)\log_{\mathrm{cfc}}(A)logcfc​(A) is the continuous functional calculus applied to the real logarithm and AAA (in particular, on positive definite Hermitian matrices it applies the usual logarithm to each eigenvalue). The assumptions impose Hermitianity and spectral bounds only almost everywhere, permit L=0L=0L=0, and impose no sign restriction on θ\thetaθ; when L=0L=0L=0 they force X=0X=0X=0 almost everywhere, so the two positive semidefinite differences are zero, and when θ=0\theta=0θ=0 the differences are likewise zero. The probability-measure assumption requires μ(Ω)=1\mu(\Omega)=1μ(Ω)=1, excluding an empty underlying space.

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