Theorem 5.1.1 — Matrix Chernoff, both spectral sides
ProvedTroppMatrixConcentration.ch5_matrix_chernoffLet be a finite independent family of measurable random complex matrices on a probability space, with . Assume each is Hermitian almost surely and satisfies and almost surely, for a common . Define , , and . Then
For every , both expectation inequalities hold:
For ,
For every ,
At both tail expressions are explicitly ; all summands then vanish almost surely. The family may be empty, and either mean eigenvalue may be zero. This goal retains every conclusion of the source theorem and the distinct lower- and upper-tail deviation domains.
import Definitions.Def_TroppMatrixConcentration_ch5_chernoff_functions open MeasureTheory ProbabilityTheory open scoped Matrix.Norms.L2Operator
namespace TroppMatrixConcentration
theorem ch5_matrix_chernoff {Ω : Type*} [MeasurableSpace Ω]
(μ : Measure Ω) [IsProbabilityMeasure μ] {d N : ℕ} [NeZero d]
(X : Fin N → Ω → Matrix (Fin d) (Fin d) ℂ) (L : ℝ) (hL : 0 ≤ L)
(hMeas : ∀ k, Measurable (X k)) (hIndep : iIndepFun X μ)
(hHerm : ∀ k, ∀ᵐ ω ∂μ, (X k ω).IsHermitian)
(hBound : ∀ k, ∀ᵐ ω ∂μ, 0 ≤ lambdaMin (X k ω) ∧ lambdaMax (X k ω) ≤ L) :
let Y := fun ω => ∑ k, X k ω
let a := lambdaMin (∫ ω, Y ω ∂μ)
let b := lambdaMax (∫ ω, Y ω ∂μ)
a = lambdaMin (∑ k, ∫ ω, X k ω ∂μ) ∧
b = lambdaMax (∑ k, ∫ ω, X k ω ∂μ) ∧
(∀ θ : ℝ, 0 < θ →
(1 - Real.exp (-θ)) / θ * a - L * Real.log d / θ ≤
(∫ ω, lambdaMin (Y ω) ∂μ) ∧
(∫ ω, lambdaMax (Y ω) ∂μ) ≤
(Real.exp θ - 1) / θ * b + L * Real.log d / θ) ∧
(∀ ε : ℝ, 0 ≤ ε → ε < 1 →
(μ {ω | lambdaMin (Y ω) ≤ (1 - ε) * a}).toReal ≤
chernoffLowerTail d a L ε) ∧
(∀ ε : ℝ, 0 ≤ ε →
(μ {ω | (1 + ε) * b ≤ lambdaMax (Y ω)}).toReal ≤
chernoffUpperTail d b L ε) := by sorry
end TroppMatrixConcentration
Read-back
What the Lean code literally says, in plain math · gpt-6
For every measurable space , every probability measure on it, natural numbers and , a family indexed by , and a real number , assume that each is measurable for the Borel measurable structure on complex matrices, that the whole family is jointly independent under , and that for each , almost surely , and almost surely both and . Here, for any complex square matrix , and , where ; these are the least and greatest eigenvalues for Hermitian , and the infimum and supremum of the empty real spectrum are both assigned the value zero. Set , , and , using Bochner integrals for matrices and real-valued functions (with the integral assigned zero when the function is not integrable). Then and ; for every real , both and hold; for every real , if , and otherwise this probability is at most ; and for every real , if , and otherwise this probability is at most . Probabilities in these inequalities are the real values of their finite measure values, all displayed powers are real powers, and is the natural logarithm. The hypotheses require no positive lower bound on , , or ; the branches use exactly without division by . The allowed value makes all family hypotheses vacuous, gives and , and makes both tail events the whole space with probability one and both tail bounds equal to ; is excluded, is allowed and gives , is excluded, is included in both tail assertions and gives bound , and is excluded only from the lower-tail assertion. Both tail events include equality, and every asserted inequality is non-strict.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.