(4.5), proof of Proposition 4.1, p. 426 — 0 ≤ ⟨C, P_ε⟩ − ⟨C, P⟩ ≤ ε(H(P_ε) − H(P))
ProvedCompOT.EntropicLimit.eq_4_5entropic-regularizationoptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1
Let , be marginals, a cost matrix and . Let be an optimal coupling of the Kantorovich problem (2.11), so , and let be an optimal solution of the entropic problem (4.2). Then
This sandwich is the core estimate in the proof of Proposition 4.1: it forces limit points of to be optimal and, after division by , to have maximal entropy.
Formalization Note The book derives (4.5) along a sequence ; the inequality holds for each fixed and is stated so. No simplex hypothesis on is needed (the hypotheses already provide couplings).
Preamble
import Mathlib import Definitions.Def_CompOT_EntropicLimit_Defs
Formal statement
namespace CompOT.EntropicLimit
/-- (4.5), proof of Proposition 4.1, p. 426: if `P` is optimal for (2.11) and `Q` is optimal
for (4.2) with `ε > 0`, then `0 ≤ ⟨C,Q⟩ - ⟨C,P⟩ ≤ ε (H(Q) - H(P))`. -/
theorem eq_4_5 {n m : ℕ} (C : Matrix (Fin n) (Fin m) ℝ)
(a : Fin n → ℝ) (b : Fin m → ℝ) (ε : ℝ) (hε : 0 < ε)
(P Q : Matrix (Fin n) (Fin m) ℝ)
(hP : CompOT.Assignment.IsOptimalCoupling C a b P) (hQ : IsEntropicOptimal C a b ε Q) :
0 ≤ CompOT.Assignment.frob C Q - CompOT.Assignment.frob C P ∧ CompOT.Assignment.frob C Q - CompOT.Assignment.frob C P ≤ ε * (entropy Q - entropy P) := by sorry
end CompOT.EntropicLimit
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), proof of Proposition 4.1, eq. (4.5), p. 426
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.