(5.2.4), p. 66 — expected spectral norm after row selection
ProvedIntroMatrixConc.Submatrix.eq_5_2_4matrix-chernoffmatrix-concentrationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1submatrix
Let , with , and let independently select rows with Bernoulli probability , where . Then
This estimates the first expectation on the right side of (5.2.3).
Formalization Note The matrix is complex and the row indicators are measurable. Their bounded support supplies integrability, which is also an explicit conclusion. The maxima range over nonempty finite index sets.
Preamble
import Definitions.Def_IntroMatrixConc_Submatrix_Defs open MeasureTheory ProbabilityTheory TroppMatrixConcentration open scoped Matrix.Norms.L2Operator
Formal statement
namespace IntroMatrixConc.Submatrix
/-- Tropp (5.2.4), p. 66: the second Chernoff bound after row selection. -/
theorem eq_5_2_4 {Ω : 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 ω => lambdaMax (selectedRows B δ ω *
(selectedRows B δ ω).conjTranspose)) μ ∧
(∫ ω, lambdaMax (selectedRows B δ ω *
(selectedRows B δ ω).conjTranspose) ∂μ) ≤
(1.72 : ℝ) * (p / (d : ℝ)) * lambdaMax (B.conjTranspose * B) +
Real.log n * maxRowSq B := by sorry
end IntroMatrixConc.Submatrix
Source
Tropp, arXiv:1501.01571v1, (5.2.4), p. 66
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.