(5.1.8), p. 61 — streamlined upper matrix Chernoff expectation bound
ProvedIntroMatrixConc.Submatrix.eq_5_1_8matrix-chernoffmatrix-concentrationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be a finite independent family of measurable, Hermitian, positive semidefinite random matrices with and almost surely, where . Set and . Then
This is the numerical form of the upper expectation estimate in Theorem 5.1.1 and the concentration step used throughout §5.2.
Formalization Note Bounded summands make the displayed eigenvalue integrable; the statement records that fact explicitly. The family may be empty and is allowed.
Preamble
import Definitions.Def_IntroMatrixConc_Submatrix_Defs open MeasureTheory ProbabilityTheory TroppMatrixConcentration open scoped Matrix.Norms.L2Operator
Formal statement
namespace IntroMatrixConc.Submatrix
/-- Tropp (5.1.8), p. 61: the streamlined upper expectation bound. -/
theorem eq_5_1_8 {Ω : 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 ω
Integrable (fun ω => lambdaMax (Y ω)) μ ∧
(∫ ω, lambdaMax (Y ω) ∂μ) ≤
(1.72 : ℝ) * lambdaMax (∫ ω, Y ω ∂μ) + L * Real.log d := by sorry
end IntroMatrixConc.Submatrix
Source
Tropp, arXiv:1501.01571v1, (5.1.8), p. 61; Theorem 5.1.1 hypotheses, p. 60
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.