(5.2.5), p. 66 — expected largest sampled column norm
ProvedIntroMatrixConc.Submatrix.eq_5_2_5matrix-chernoffmatrix-concentrationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1submatrix
Let , with , and let independently select rows with Bernoulli probability , where . Then
This controls the remaining expectation in (5.2.3), involving the largest sampled column.
Formalization Note The maxima are finite and nonempty, and the bounded Bernoulli model makes the sampled-column maximum integrable; that fact is stated explicitly.
Preamble
import Definitions.Def_IntroMatrixConc_Submatrix_Defs open MeasureTheory ProbabilityTheory TroppMatrixConcentration open scoped Matrix.Norms.L2Operator
Formal statement
namespace IntroMatrixConc.Submatrix
/-- Tropp (5.2.5), p. 66: the maximum sampled column norm. -/
theorem eq_5_2_5 {Ω : Type*} [MeasurableSpace Ω]
(μ : Measure Ω) [IsProbabilityMeasure μ] {d n : ℕ} [NeZero d] [NeZero n]
(B : Matrix (Fin d) (Fin n) ℂ) (δ : Fin d → Ω → ℝ) (p : ℝ)
(hp0 : 0 ≤ p) (hpd : p ≤ (d : ℝ))
(hδMeas : ∀ j, Measurable (δ j)) (hIndep : iIndepFun δ μ)
(hδ : ∀ j, IsBernoulli μ (δ j) (p / (d : ℝ))) :
Integrable (fun ω => maxSelectedColumnSq B δ ω) μ ∧
(∫ ω, maxSelectedColumnSq B δ ω ∂μ) ≤
(1.72 : ℝ) * (p / (d : ℝ)) * maxColumnSq B +
Real.log n * maxEntrySq B := by sorry
end IntroMatrixConc.Submatrix
Source
Tropp, arXiv:1501.01571v1, (5.2.5), p. 66
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.