(9.18), pp. 530–531 — column-potential block maximizer
ProvedCompOT.Barycenter.g_block_maximizeroptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1sinkhornwasserstein-barycenter
Fix a nonempty barycenter support, a cost matrix , a positive regularization parameter , a strictly positive target histogram , and a row potential . Put and . In the dual objective, the column potential maximizes its block when
This gives at least as large a block objective as any other column potential.
The identity is the dual interpretation of the column-scaling update in (9.18).
Formalization Note The page says “minimizing (9.21)” although (9.21) is displayed as a maximum. The theorem uses maximization. Positive permits the logarithm, and the nonempty row index makes its denominator positive.
Preamble
import Mathlib import Definitions.Def_CompOT_Barycenter_Defs
Formal statement
namespace CompOT.Barycenter
/-- The column-potential block optimum is the scaling update (9.18),
as stated after Proposition 9.1 on pp. 530–531. -/
theorem g_block_maximizer {n m : ℕ} (hn : 0 < n) (hm : 0 < m)
(ε : ℝ) (hε : 0 < ε) (C : Matrix (Fin n) (Fin m) ℝ)
(b : Fin m → ℝ) (hbSimplex : b ∈ stdSimplex ℝ (Fin m))
(hb : ∀ j, 0 < b j) (f : Fin n → ℝ) :
(∀ g : Fin m → ℝ,
gBlockObjective ε C b f g ≤
gBlockObjective ε C b f (gBlockUpdate ε C b f)) ∧
(∀ j, Real.exp (gBlockUpdate ε C b f j / ε) =
b j / (∑ i, gibbs ε C i j * Real.exp (f i / ε))) := by sorry
end CompOT.Barycenter
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), (9.18), p. 529; paragraph after proof of Proposition 9.1, pp. 530–531
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.