(5.2.2), p. 65 — expected squared norm of a random row-and-column submatrix
ProvedIntroMatrixConc.Submatrix.eq_5_2_2matrix-chernoffmatrix-concentrationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1submatrix
Let , with . Independently select its rows with probability and its columns with probability , where and . Let and be the diagonal zero-one projectors recording the selections, and set . Then
The estimate separates a term involving the whole matrix from fluctuations controlled by its largest column, row, and entry.
Formalization Note The indicators for all rows and columns are one jointly independent measurable family. The book's simplified constants and are used exactly. Integrability of is asserted explicitly under the bounded Bernoulli model; keep every maximum and logarithm in its intended domain.
Preamble
import Definitions.Def_IntroMatrixConc_Submatrix_Defs open MeasureTheory ProbabilityTheory TroppMatrixConcentration open scoped Matrix.Norms.L2Operator
Formal statement
namespace IntroMatrixConc.Submatrix
/-- Tropp (5.2.2), p. 65: the row-and-column random submatrix expectation bound. -/
theorem eq_5_2_2 {Ω : Type*} [MeasurableSpace Ω]
(μ : Measure Ω) [IsProbabilityMeasure μ] {d n : ℕ} [NeZero d] [NeZero n]
(B : Matrix (Fin d) (Fin n) ℂ) (δ : Fin d → Ω → ℝ)
(ξ : Fin n → Ω → ℝ) (p r : ℝ)
(hp0 : 0 ≤ p) (hpd : p ≤ (d : ℝ))
(hr0 : 0 ≤ r) (hrn : r ≤ (n : ℝ))
(hδMeas : ∀ j, Measurable (δ j)) (hξMeas : ∀ k, Measurable (ξ k))
(hIndep : iIndepFun (Sum.elim δ ξ) μ)
(hδ : ∀ j, IsBernoulli μ (δ j) (p / (d : ℝ)))
(hξ : ∀ k, IsBernoulli μ (ξ k) (r / (n : ℝ))) :
Integrable (fun ω => spectralNorm (selectedSubmatrix B δ ξ ω) ^ 2) μ ∧
(∫ ω, spectralNorm (selectedSubmatrix B δ ξ ω) ^ 2 ∂μ) ≤
(3 : ℝ) * (p / (d : ℝ)) * (r / (n : ℝ)) * spectralNorm B ^ 2 +
2 * (p * Real.log d / (d : ℝ)) * maxColumnSq B +
2 * (r * Real.log n / (n : ℝ)) * maxRowSq B +
Real.log d * Real.log n * maxEntrySq B := by sorry
end IntroMatrixConc.Submatrix
Source
Tropp, arXiv:1501.01571v1, (5.2.2), p. 65; simplification note, p. 66
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.