Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.6.3 — Rademacher matrix mgf and cgf bounds

Proved
TroppMatrixConcentration.ch4_rademacher_mgf_cgf

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

matrix-concentrationrandom-matrices

Let AAA be a fixed Hermitian complex d×dd\times dd×d matrix, d≥1d\ge1d≥1, and let ggg be a measurable Rademacher random variable on a probability space, taking −1-1−1 and 111 with probabilities one half each. For every real θ\thetaθ,

EeθgA⪯eθ2A2/2,log⁡EeθgA⪯θ2A2/2.\mathbb E e^{\theta gA}\preceq e^{\theta^2 A^2/2},\qquad\log\mathbb E e^{\theta gA}\preceq\theta^2 A^2/2.EeθgA⪯eθ2A2/2,logEeθgA⪯θ2A2/2.

Both relations are in positive-semidefinite order. The actual two-point distribution is required, not merely its mean and variance. No sign restriction is placed on θ\thetaθ.

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_rademacher_mgf_cgf {Ω : Type*} [MeasurableSpace Ω]
    (μ : Measure Ω) [IsProbabilityMeasure μ] {d : ℕ} [NeZero d]
    (A : Matrix (Fin d) (Fin d) ℂ) (hA : A.IsHermitian)
    (g : Ω → ℝ) (hMeas : Measurable g) (hLaw : rademacherLaw μ g) (θ : ℝ) :
    loewnerLE (∫ ω, matrixExp ((θ * g ω) • A) ∂μ) (matrixExp ((θ ^ 2 / 2) • A ^ 2)) ∧
    loewnerLE (matrixLog (∫ ω, matrixExp ((θ * g ω) • A) ∂μ)) ((θ ^ 2 / 2) • A ^ 2) := 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 4.6.3, printed p. 54.
Read-back

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

For every type Ω\OmegaΩ equipped with a measurable space, every probability measure μ\muμ on that space (so μ(Ω)=1\mu(\Omega)=1μ(Ω)=1), every natural number d≠0d\ne0d=0, every complex d×dd\times dd×d matrix AAA indexed by {0,…,d−1}\{0,\ldots,d-1\}{0,…,d−1} satisfying A∗=AA^*=AA∗=A, every measurable function g:Ω→Rg:\Omega\to\mathbb Rg:Ω→R whose pushforward measure is g∗μ=12δ1+12δ−1g_*\mu=\tfrac12\delta_1+\tfrac12\delta_{-1}g∗​μ=21​δ1​+21​δ−1​, and every real number θ\thetaθ, put M=∫Ωexp⁡((θg(ω))A) dμ(ω)M=\int_\Omega \exp((\theta g(\omega))A)\,d\mu(\omega)M=∫Ω​exp((θg(ω))A)dμ(ω) and B=(θ2/2)A2B=(\theta^2/2)A^2B=(θ2/2)A2. Then both M⪯exp⁡(B)M\preceq\exp(B)M⪯exp(B) and Log⁡(M)⪯B\operatorname{Log}(M)\preceq BLog(M)⪯B hold. Here δa\delta_aδa​ is the unit point mass at aaa, the integral is the matrix-valued Bochner integral, scalar multiplication uses real scalars acting on complex entries, A2=AAA^2=AAA2=AA is the matrix product, and exp⁡(C)=∑n=0∞Cn/n!\exp(C)=\sum_{n=0}^{\infty}C^n/n!exp(C)=∑n=0∞​Cn/n! is the matrix exponential. The notation C⪯DC\preceq DC⪯D means exactly that D−CD-CD−C is Hermitian and z∗(D−C)zz^*(D-C)zz∗(D−C)z is a nonnegative real number for every z∈Cdz\in\mathbb C^dz∈Cd. The function Log⁡\operatorname{Log}Log is the real continuous functional calculus applied to the total real logarithm: on a Hermitian matrix with a unitary diagonalization C=Udiag⁡(λ1,…,λd)U∗C=U\operatorname{diag}(\lambda_1,\ldots,\lambda_d)U^*C=Udiag(λ1​,…,λd​)U∗, it gives Udiag⁡(ℓ(λ1),…,ℓ(λd))U∗U\operatorname{diag}(\ell(\lambda_1),\ldots,\ell(\lambda_d))U^*Udiag(ℓ(λ1​),…,ℓ(λd​))U∗, where ℓ(t)=log⁡∣t∣\ell(t)=\log|t|ℓ(t)=log∣t∣ for t≠0t\ne0t=0 and ℓ(0)=0\ell(0)=0ℓ(0)=0; the real functional calculus returns zero on non-Hermitian matrices (and in general when its scalar function is not continuous on the real spectrum). The law of ggg is an equality of measures, so its values outside {−1,1}\{-1,1\}{−1,1} are permitted on a measurable null set; it gives each of the events {g=1}\{g=1\}{g=1} and {g=−1}\{g=-1\}{g=−1} measure 1/21/21/2. The zero dimension is excluded, whereas d=1d=1d=1, A=0A=0A=0, singular Hermitian AAA, and all negative, zero, and positive θ\thetaθ are included; if θ=0\theta=0θ=0 or A=0A=0A=0, then M=IdM=I_dM=Id​ and B=0B=0B=0, and both displayed inequalities are equalities. No separate integrability or positive-definiteness hypothesis is imposed; under the stated law the integrand takes two matrix values almost everywhere and MMM is positive definite. An empty Ω\OmegaΩ cannot carry the required probability measure.

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