Proof of Corollary 6.2.1 — centered summand bound
ProvedIntroMatrixConc.Sampling.summand_boundmatrix-concentrationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1sampling
Let be independent copies of a measurable complex random matrix , where and . Suppose and almost surely. Define the centered, scaled summands . Then are independent and identically distributed, each has , and for every
These are the hypotheses of the matrix Bernstein inequality that the proof of Corollary 6.2.1 checks for the estimator error .
Formalization Note "Independent copy" is iIndepFun of the family together with equality in law (IdentDistrib) to a reference matrix ; the almost-sure bound is the page's . The statement includes the page's preceding sentence (i.i.d. family, mean zero) as well as the displayed norm bound.
Preamble
import Definitions.Def_IntroMatrixConc_Sampling_Defs import Mathlib.Probability.IdentDistrib open MeasureTheory ProbabilityTheory TroppMatrixConcentration open scoped Matrix.Norms.L2Operator noncomputable section
Formal statement
namespace IntroMatrixConc.Sampling
/-- Tropp, proof of Corollary 6.2.1, p. 82 (PDF p. 88): the centered summands are i.i.d.,
have mean zero, and satisfy `‖S_k‖ ≤ 2L/n` almost surely. -/
theorem summand_bound {Ω : Type*} [MeasurableSpace Ω]
(μ : Measure Ω) [IsProbabilityMeasure μ]
{d₁ d₂ n : ℕ} [NeZero d₁] [NeZero d₂]
(R₀ : Ω → Matrix (Fin d₁) (Fin d₂) ℂ)
(R : Fin n → Ω → Matrix (Fin d₁) (Fin d₂) ℂ)
(B : Matrix (Fin d₁) (Fin d₂) ℂ) (L : ℝ)
(hn : 0 < n)
(hMeas₀ : Measurable R₀) (hMeas : ∀ k, Measurable (R k))
(hIndep : iIndepFun R μ)
(hCopies : ∀ k, IdentDistrib (R k) R₀ μ μ)
(hMean : (∫ ω, R₀ ω ∂μ) = B)
(hBound : ∀ᵐ ω ∂μ, spectralNorm (R₀ ω) ≤ L) :
let S := fun (k : Fin n) (ω : Ω) => ((n : ℝ)⁻¹) • (R k ω - B)
iIndepFun S μ ∧ (∀ k j, IdentDistrib (S k) (S j) μ μ) ∧
(∀ k, (∫ ω, S k ω ∂μ) = 0) ∧
∀ k, ∀ᵐ ω ∂μ, spectralNorm (S k ω) ≤ 2 * L / n := by sorry
end IntroMatrixConc.Sampling
Source
Tropp, arXiv:1501.01571v1, §6.2.2, proof of Corollary 6.2.1, p. 82 (PDF p. 88), summand-bound display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.