Proposition 3.1, pp. 403–404 — f ≤ f′ ⇒ f^C ≥ f′^C; f^{CC̄} ≥ f, g^{C̄C} ≥ g; f^{CC̄C} = f^C
ProvedCompOT.Duality.proposition_3_1c-transformoptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1
Let and . For and write and . With inequalities between vectors read elementwise:
- for all ;
- for all , and for all ;
- for all .
Here and so on. The proposition explains why alternating - and -transforms to improve the dual objective stalls after one round.
Formalization Note The hypotheses and make both minima well defined (the book's index sets are nonempty).
Preamble
import Mathlib import Definitions.Def_CompOT_Duality_Defs
Formal statement
namespace CompOT.Duality
/-- Proposition 3.1, pp. 403–404 (elementwise order on vectors):
(i) `f ≤ f′ ⇒ f^C ≥ f′^C`; (ii) `f^{C C̄} ≥ f` and `g^{C̄ C} ≥ g`; (iii) `f^{C C̄ C} = f^C`.
Both index sets are nonempty (`n, m ≥ 1`), so that the transforms are genuine minima. -/
theorem proposition_3_1 {n m : ℕ} (hn : 0 < n) (hm : 0 < m) (C : Matrix (Fin n) (Fin m) ℝ) :
(∀ f f' : Fin n → ℝ, f ≤ f' → cTransform C f' ≤ cTransform C f) ∧
(∀ f : Fin n → ℝ, f ≤ cbarTransform C (cTransform C f)) ∧
(∀ g : Fin m → ℝ, g ≤ cTransform C (cbarTransform C g)) ∧
(∀ f : Fin n → ℝ, cTransform C (cbarTransform C (cTransform C f)) = cTransform C f) := by sorry
end CompOT.Duality
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), Proposition 3.1, pp. 403–404
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.