Corollary 6.2.1 — matrix approximation by random sampling
ProvedIntroMatrixConc.Sampling.corollary_6_2_1matrix-bernsteinmatrix-concentrationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1sampling
Let be a fixed complex matrix, where . Let be a measurable random matrix of the same size with and almost surely. Form from independent copies of . Define
The estimator error has finite expected spectral norm, and
For every , it also satisfies
This gives both an expectation guarantee and a tail guarantee for empirical matrix approximation.
Formalization Note The almost-sure bound and measurability make the displayed expectations genuine Bochner integrals; the integrability of the error norm is also asserted explicitly. At a zero tail denominator, Lean's division convention makes the right side , a valid but loose 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, Corollary 6.2.1, p. 81 (PDF p. 87), equations (6.2.5) and (6.2.6). -/
theorem corollary_6_2_1 {Ω : 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) :
Integrable (fun ω => spectralNorm (samplingEstimator R ω - B)) μ ∧
(∫ ω, spectralNorm (samplingEstimator R ω - B) ∂μ) ≤
Real.sqrt (2 * rectSecondMoment μ R₀ * Real.log (d₁ + d₂) / n) +
2 * L * Real.log (d₁ + d₂) / (3 * n) ∧
∀ t : ℝ, 0 ≤ t →
(μ {ω | t ≤ spectralNorm (samplingEstimator R ω - B)}).toReal ≤
(d₁ + d₂ : ℕ) * Real.exp
((-((n : ℝ) * t ^ 2) / 2) /
(rectSecondMoment μ R₀ + 2 * L * t / 3)) := by sorry
end IntroMatrixConc.Sampling
Source
Tropp, arXiv:1501.01571v1, Corollary 6.2.1, equations (6.2.4)–(6.2.6), p. 81 (PDF p. 87)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.