Proof of Proposition 2.2, p. 378 — the glued matrix S = P diag(1/b̃) Q lies in U(a, c)
ProvedCompOT.Metric.prop_2_2_gluinggluingoptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1transportation-polytope
Let , and . Let if and otherwise. Then
This is the discrete gluing lemma: is nonnegative, its row sums are and its column sums are . It is the coupling used to compare with .
Formalization Note The page takes and optimal; the membership claim does not use optimality, so it is stated for every and , which contains the page's case.
Preamble
import Mathlib import Definitions.Def_CompOT_Metric_Defs
Formal statement
namespace CompOT.Metric
open Matrix
/-- Proof of Proposition 2.2, p. 378: for `a, b, c ∈ Σ_n`, `P ∈ U(a, b)` and
`Q ∈ U(b, c)`, the glued matrix `S = P diag(1/b̃) Q` is nonnegative and lies in `U(a, c)`.
(The page takes `P`, `Q` optimal; optimality is not used for this claim.) -/
theorem prop_2_2_gluing {n : ℕ} (a b c : Fin n → ℝ)
(ha : a ∈ stdSimplex ℝ (Fin n)) (hb : b ∈ stdSimplex ℝ (Fin n))
(hc : c ∈ stdSimplex ℝ (Fin n))
(P Q : Matrix (Fin n) (Fin n) ℝ) (hP : P ∈ CompOT.Assignment.couplings a b) (hQ : Q ∈ CompOT.Assignment.couplings b c) :
glue b P Q ∈ CompOT.Assignment.couplings a c := by sorry
end CompOT.Metric
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), proof of Proposition 2.2, p. 378
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.