(4.7), p. 428 — P_ε is the KL projection of the Gibbs kernel K = e^{−C/ε} onto U(a, b)
ProvedCompOT.EntropicLimit.eq_4_7bregman-projectionentropic-regularizationkullback-leibleroptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1
Let , be marginals, a cost matrix, , and let be the Gibbs kernel. A matrix solves the entropic problem (4.2) if and only if it solves the Kullback–Leibler projection problem
In particular the unique solution of (4.2) is the KL projection of onto .
This reformulation is the starting point of Sinkhorn's algorithm.
Formalization Note Stated as an equivalence of the two optimality predicates for every matrix ; uses .
Preamble
import Mathlib import Definitions.Def_CompOT_EntropicLimit_Defs
Formal statement
namespace CompOT.EntropicLimit
/-- (4.7), p. 428: for `ε > 0`, a matrix solves (4.2) if and only if it minimizes
`KL(·|K)` over `U(a,b)`, where `K` is the Gibbs kernel `K_{i,j} = exp(-C_{i,j}/ε)`. -/
theorem eq_4_7 {n m : ℕ} (C : Matrix (Fin n) (Fin m) ℝ)
(a : Fin n → ℝ) (b : Fin m → ℝ) (ε : ℝ) (hε : 0 < ε)
(P : Matrix (Fin n) (Fin m) ℝ) :
IsEntropicOptimal C a b ε P ↔
(P ∈ CompOT.Assignment.couplings a b ∧
∀ Q ∈ CompOT.Assignment.couplings a b, klMat P (gibbs C ε) ≤ klMat Q (gibbs C ε)) := by sorry
end CompOT.EntropicLimit
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), (4.6)–(4.7), p. 428
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.