Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Matrix second moments, cumulant sums, and Bernstein tail expression

Definition
TroppMatrixConcentration_probability

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

matrix-concentrationrandom-matrices

Equip complex matrix spaces with the Borel sigma-algebra of their product topology. For matrix-valued functions on a measure space, define the uncentered rectangular second-moment statistic max⁡{∥∫ZZ∗∥,∥∫Z∗Z∥}\max\{\|\int ZZ^*\|,\|\int Z^*Z\|\}max{∥∫ZZ∗∥,∥∫Z∗Z∥}, the Hermitian second-moment statistic ∥∫Y2∥\|\int Y^2\|∥∫Y2∥, and the finite cumulant sum K(θ)=∑klog⁡∫eθXkK(\theta)=\sum_k\log\int e^{\theta X_k}K(θ)=∑k​log∫eθXk​. Centering is supplied explicitly by callers; the concentration statements use zero-mean random matrices. The Bernstein tail expression is dexp⁡(−(t2/2)/(v+Lt/3))d\exp(-(t^2/2)/(v+Lt/3))dexp(−(t2/2)/(v+Lt/3)) when the denominator is nonzero. When it is zero the expression is defined as ddd at t=0t=0t=0 and zero otherwise. Probability, integrability, Hermitian, and positivity assumptions belong to the theorem statements, not to these total definitions.

Definition code
import Definitions.Def_TroppMatrixConcentration_spectral
import Mathlib.MeasureTheory.Integral.Bochner.Basic
import Mathlib.Probability.Independence.Basic
import Mathlib.MeasureTheory.Function.LpSeminorm.Basic
import Mathlib.MeasureTheory.Constructions.BorelSpace.Complex

open MeasureTheory
open scoped Matrix.Norms.L2Operator

noncomputable section
namespace TroppMatrixConcentration

instance matrixMeasurableSpace {m n : Type*} : MeasurableSpace (Matrix m n ℂ) :=
  borel (Matrix m n ℂ)

instance matrixBorelSpace {m n : Type*} : BorelSpace (Matrix m n ℂ) := ⟨rfl⟩

def rectSecondMoment {Ω m n : Type*} [MeasurableSpace Ω]
    [Fintype m] [Fintype n] [DecidableEq m] [DecidableEq n]
    (μ : Measure Ω) (Z : Ω → Matrix m n ℂ) : ℝ :=
  max (spectralNorm (∫ ω, Z ω * (Z ω).conjTranspose ∂μ))
      (spectralNorm (∫ ω, (Z ω).conjTranspose * Z ω ∂μ))

def hermitianSecondMoment {Ω d : Type*} [MeasurableSpace Ω]
    [Fintype d] [DecidableEq d] (μ : Measure Ω) (Y : Ω → Matrix d d ℂ) : ℝ :=
  spectralNorm (∫ ω, Y ω ^ 2 ∂μ)

def cumulantSum {Ω d : Type*} [MeasurableSpace Ω]
    [Fintype d] [DecidableEq d] {N : ℕ}
    (μ : Measure Ω) (X : Fin N → Ω → Matrix d d ℂ) (θ : ℝ) : Matrix d d ℂ :=
  ∑ k, matrixLog (∫ ω, matrixExp (θ • X k ω) ∂μ)

def bernsteinTail (dimension : ℕ) (v L t : ℝ) : ℝ :=
  if v + L * t / 3 = 0 then
    if t = 0 then (dimension : ℝ) else 0
  else (dimension : ℝ) * Real.exp (-(t ^ 2 / 2) / (v + L * t / 3))

end TroppMatrixConcentration
Source
Joel A. Tropp, An Introduction to Matrix Concentration Inequalities, arXiv:1501.01571v1 (7 January 2015); https://arxiv.org/abs/1501.01571v1; Sections 2.2.4 and 2.2.6–2.2.8; equations (3.6.1–4), (6.1.1), (6.1.4), and (6.6.1–3); printed pp. 26–29, 36, 76, 96.
Read-back

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

TroppMatrixConcentration.matrixMeasurableSpace. For arbitrary types m,nm,nm,n, this equips the set Cm×n\mathbb C^{m\times n}Cm×n of complex matrices, viewed as functions assigning a complex number to each row and column index, with the Borel sigma algebra generated by its open sets in the product topology inherited from the usual topology on C\mathbb CC. No finiteness, countability, decidable-equality, nonemptiness, or additional structure assumptions on either index type are imposed. Infinite index types are included; the sigma algebra is specified as the Borel sigma algebra of the product topology. If either index type is empty, the matrix space is a singleton and this is its unique sigma algebra.

TroppMatrixConcentration.matrixBorelSpace. For arbitrary types m,nm,nm,n, this supplies the assertion that the measurable-space structure on Cm×n\mathbb C^{m\times n}Cm×n provided by matrixMeasurableSpace is exactly the Borel sigma algebra of the product topology inherited from C\mathbb CC; the assertion holds by the defining equality of that measurable-space structure. It requires no hypotheses on the index types, including no finiteness, countability, decidable-equality, or nonemptiness assumptions. Empty index types are included, in which case the matrix space is a singleton with its unique sigma algebra.

TroppMatrixConcentration.rectSecondMoment. For any type Ω\OmegaΩ equipped with a measurable space, any finite index types m,nm,nm,n equipped with finite enumerations and decidable equality, any measure μ\muμ on Ω\OmegaΩ, and any function Z:Ω→Cm×nZ:\Omega\to\mathbb C^{m\times n}Z:Ω→Cm×n, this defines the real number max⁡{∥∫Z(ω)Z(ω)∗ dμ(ω)∥2→2,∥∫Z(ω)∗Z(ω) dμ(ω)∥2→2}\max\{\|\int Z(\omega)Z(\omega)^*\,d\mu(\omega)\|_{2\to2},\|\int Z(\omega)^*Z(\omega)\,d\mu(\omega)\|_{2\to2}\}max{∥∫Z(ω)Z(ω)∗dμ(ω)∥2→2​,∥∫Z(ω)∗Z(ω)dμ(ω)∥2→2​}, where A∗A^*A∗ is the conjugate transpose, products are matrix products, the two integrals are respectively m×mm\times mm×m and n×nn\times nn×n matrix-valued Bochner integrals, and ∥⋅∥2→2\|\cdot\|_{2\to2}∥⋅∥2→2​ is the operator norm induced by Euclidean norms. There is no assumption that μ\muμ is finite or a probability measure, or that ZZZ or either product is measurable or integrable. Each integral individually has the value zero when its integrand is not Bochner integrable, so if both integrands fail integrability the defined number is zero. Empty index types are allowed; if either mmm or nnn is empty the number is zero. The measurable domain may also be empty, and the zero measure is permitted, in either case giving zero.

TroppMatrixConcentration.hermitianSecondMoment. For any type Ω\OmegaΩ equipped with a measurable space, any finite index type ddd equipped with a finite enumeration and decidable equality, any measure μ\muμ on Ω\OmegaΩ, and any function Y:Ω→Cd×dY:\Omega\to\mathbb C^{d\times d}Y:Ω→Cd×d, this defines the real number ∥∫Y(ω)2 dμ(ω)∥2→2\|\int Y(\omega)^2\,d\mu(\omega)\|_{2\to2}∥∫Y(ω)2dμ(ω)∥2→2​, with a matrix-valued Bochner integral and the Euclidean operator norm. Here Y(ω)2Y(\omega)^2Y(ω)2 is the matrix product Y(ω)Y(ω)Y(\omega)Y(\omega)Y(ω)Y(ω), with no conjugate transpose. No Hermitian, positivity, centering, measurability, or integrability condition on YYY is imposed, and μ\muμ need not be finite or a probability measure. If the square-valued integrand is not Bochner integrable, its integral and hence the defined number are zero. An empty ddd, an empty Ω\OmegaΩ, and the zero measure are all allowed and give zero.

TroppMatrixConcentration.cumulantSum. For any type Ω\OmegaΩ equipped with a measurable space, any finite index type ddd equipped with a finite enumeration and decidable equality, any natural number NNN, any measure μ\muμ on Ω\OmegaΩ, any family of functions Xk:Ω→Cd×dX_k:\Omega\to\mathbb C^{d\times d}Xk​:Ω→Cd×d indexed by k∈{0,…,N−1}k\in\{0,\ldots,N-1\}k∈{0,…,N−1}, and any real θ\thetaθ, this defines the matrix ∑k=0N−1L(∫exp⁡(θXk(ω)) dμ(ω))\sum_{k=0}^{N-1}\mathcal L(\int \exp(\theta X_k(\omega))\,d\mu(\omega))∑k=0N−1​L(∫exp(θXk​(ω))dμ(ω)). Scalar multiplication is by the real number θ\thetaθ, the exponential is the matrix exponential exp⁡(A)=∑j=0∞Aj/j!\exp(A)=\sum_{j=0}^{\infty}A^j/j!exp(A)=∑j=0∞​Aj/j!, and the integral is the matrix-valued Bochner integral, defined to be zero when its integrand is not Bochner integrable. The function L(A)\mathcal L(A)L(A) is real continuous functional calculus applied to the total real logarithm: it returns zero if AAA is not self-adjoint or if that logarithm is not continuous on the real spectrum of AAA; otherwise it applies the logarithm to the spectrum through continuous functional calculus. For a finite Hermitian matrix it therefore replaces each nonzero real eigenvalue λ\lambdaλ by log⁡∣λ∣\log|\lambda|log∣λ∣ and each zero eigenvalue by zero, preserving the corresponding eigenspaces. In particular, L(0)=0\mathcal L(0)=0L(0)=0, so a nonintegrable exponential integrand contributes a zero summand. There are no independence, self-adjointness, positivity, measurability, integrability, or centering hypotheses on the family, no sign restriction on θ\thetaθ, and no finiteness or probability assumption on μ\muμ. The case N=0N=0N=0 is included and yields the zero matrix; an empty ddd yields the unique empty matrix, and an empty Ω\OmegaΩ or zero measure yields the zero matrix.

TroppMatrixConcentration.bernsteinTail. For every natural number DDD and arbitrary real numbers v,L,tv,L,tv,L,t, this defines a real number by setting a=v+Lt/3a=v+Lt/3a=v+Lt/3 and returning DDD (viewed as a real number) when a=0a=0a=0 and t=0t=0t=0, zero when a=0a=0a=0 and t≠0t\ne0t=0, and Dexp⁡(−(t2/2)/a)D\exp(-(t^2/2)/a)Dexp(−(t2/2)/a) when a≠0a\ne0a=0. Thus the zero-denominator cases are handled by an explicit branch, including v=L=t=0v=L=t=0v=L=t=0. There are no nonnegativity assumptions on v,L,tv,L,tv,L,t and no requirement that DDD be positive: D=0D=0D=0 gives zero in every case, while t=0t=0t=0 gives DDD for every v,Lv,Lv,L. If a<0a<0a<0 and D>0D>0D>0 and t≠0t\ne0t=0, the returned value exceeds DDD; the definition imposes no bound by one and contains no measure or event.

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