Theorem 7.2.1 — Intrinsic matrix Chernoff
ProvedTroppMatrixConcentration.ch7_intrinsic_chernoffLet be a finite independent family of measurable positive semidefinite complex random matrices, , satisfying almost surely, with . Set . Let be a semidefinite upper bound for , and put and . Then for every ,
For every ,
Lean writes the bracketed power as , an equal expression on this domain. The nonzero proxy ensures . Both expectation and tail conclusions of the source are included; there is no lower-tail claim. The family may be empty.
The displayed expectation identity is also an explicit conclusion.
import Definitions.Def_TroppMatrixConcentration_ch7_intrinsic open MeasureTheory ProbabilityTheory open scoped Matrix.Norms.L2Operator ComplexOrder
namespace TroppMatrixConcentration
theorem ch7_intrinsic_chernoff {Ω : Type*} [MeasurableSpace Ω]
(μ : Measure Ω) [IsProbabilityMeasure μ] {d N : ℕ} [NeZero d]
(X : Fin N → Ω → Matrix (Fin d) (Fin d) ℂ)
(L : ℝ) (hL : 0 < L) (M : Matrix (Fin d) (Fin d) ℂ) (hM : M ≠ 0)
(hMeas : ∀ k, Measurable (X k)) (hIndep : iIndepFun X μ)
(hPSD : ∀ k, ∀ᵐ ω ∂μ, (X k ω).PosSemidef)
(hBound : ∀ k, ∀ᵐ ω ∂μ, lambdaMax (X k ω) ≤ L)
(hMeanBound : loewnerLE (∫ ω, ∑ k, X k ω ∂μ) M) :
let Y := fun ω => ∑ k, X k ω
let r := intrinsicDimension M
let a := lambdaMax M
(∫ ω, Y ω ∂μ) = ∑ k, ∫ ω, X k ω ∂μ ∧
(∀ θ : ℝ, 0 < θ → (∫ ω, lambdaMax (Y ω) ∂μ) ≤
(Real.exp θ - 1) / θ * a + L / θ * Real.log (2 * r)) ∧
∀ ε : ℝ, L / a ≤ ε →
(μ {ω | (1 + ε) * a ≤ lambdaMax (Y ω)}).toReal ≤
2 * r * Real.exp (a / L * (ε - (1 + ε) * Real.log (1 + ε))) := 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 with , a family indexed by , a real number , and a nonzero matrix , assume that every is measurable for the Borel measurable structure on matrices, that the family is mutually independent under , that for every the matrix is positive semidefinite for -almost every , and that for every one has for -almost every . Here is the supremum in of the spectrum of the complex matrix regarded as an element of an algebra over ; equivalently its spectrum consists of real scalars for which is not invertible. Assume also that is positive semidefinite. Set , , where the denominator is the operator norm for Euclidean norms, and . The assertion is the conjunction of the following three conclusions:
for every real ,
and for every real satisfying ,
The measure on the left of the last inequality is converted from its extended nonnegative real value to a real number; it is finite since is a probability measure. All integrals are Bochner integrals. The quantification includes , when the sums and are zero and the assumptions on the family and its independence are vacuous, while the mean bound requires to be positive semidefinite. There is no separate hypothesis declaring Hermitian or positive semidefinite, no separate integrability hypothesis, and no separate positivity hypothesis for or ; these quantities are used exactly as defined above. The definitions are total: real division by zero is zero, the real logarithm at zero is zero and at a negative real number is the logarithm of its absolute value, the real supremum of the empty set is zero, and a nonintegrable function has Bochner integral zero. The displayed statement uses the non-strict tail event and the non-strict threshold condition exactly as written.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.