Remark 4.21, (4.35)–(4.36) — exact log-domain block updates
ProvedCompOT.EntropicDual.remark_4_21_updatesentropyoptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1sinkhorn
Let and have strictly positive entries and let . For any fixed , the unique maximizer of is
Symmetrically, for fixed , the unique maximizer of is
Alternating these exact block maximizers is the log-domain form of Sinkhorn's scaling updates.
Formalization Note The statement compares the dual objective with every vector in each block and characterizes equality, which gives uniqueness. Positivity makes both logarithms meaningful.
Preamble
import Mathlib import Definitions.Def_CompOT_EntropicDual_Defs
Formal statement
namespace CompOT.EntropicDual
/-- Remark 4.21, (4.35)–(4.36), p. 449: each log-domain update is the
unique maximizer of the dual objective with the other potential fixed. -/
theorem remark_4_21_updates {n m : ℕ} (C : Matrix (Fin n) (Fin m) ℝ)
(a : Fin n → ℝ) (b : Fin m → ℝ) (ε : ℝ)
(hn : 0 < n) (hm : 0 < m) (hε : 0 < ε)
(ha : a ∈ stdSimplex ℝ (Fin n)) (hb : b ∈ stdSimplex ℝ (Fin m))
(ha_pos : ∀ i, 0 < a i) (hb_pos : ∀ j, 0 < b j) :
(∀ g f, dualObjEnt C a b ε f g ≤ dualObjEnt C a b ε (updateF C a ε g) g ∧
(dualObjEnt C a b ε f g = dualObjEnt C a b ε (updateF C a ε g) g →
f = updateF C a ε g)) ∧
(∀ f g, dualObjEnt C a b ε f g ≤ dualObjEnt C a b ε f (updateG C b ε f) ∧
(dualObjEnt C a b ε f g = dualObjEnt C a b ε f (updateG C b ε f) →
g = updateG C b ε f)) := by sorry
end CompOT.EntropicDual
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), Remark 4.21, (4.35)–(4.36), p. 449. https://doi.org/10.1561/2200000073
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.