Proof of Proposition 2.2, pp. 378–379 — ⟨S, D^p⟩^{1/p} ≤ ⟨P, D^p⟩^{1/p} + ⟨Q, D^p⟩^{1/p} for the glued S
ProvedCompOT.Metric.prop_2_2_minkowskiminkowski-inequalityoptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1wasserstein
Let be a distance on , , , , , and let be the glued coupling. Then
This is the chain of inequalities of pp. 378–379 (the triangle inequality of followed by Minkowski's inequality), together with its final identities and . With the gluing lemma and the suboptimality of it yields the triangle inequality for once and are optimal.
Formalization Note The page applies the chain to optimal and ; the inequality does not use optimality and is stated for all couplings. The page's two final equalities are folded into the right-hand side.
Preamble
import Mathlib import Definitions.Def_CompOT_Metric_Defs
Formal statement
namespace CompOT.Metric
open Matrix
/-- Proof of Proposition 2.2, pp. 378–379 (the chain after "The triangle inequality
follows then from", with its two final equalities): for `P ∈ U(a, b)`, `Q ∈ U(b, c)` and
`S = P diag(1/b̃) Q`, `⟨S, D^p⟩^{1/p} ≤ ⟨P, D^p⟩^{1/p} + ⟨Q, D^p⟩^{1/p}`. -/
theorem prop_2_2_minkowski {n : ℕ} (D : Matrix (Fin n) (Fin n) ℝ) (p : ℝ) (hp : 1 ≤ p)
(hD_nonneg : ∀ i j, 0 ≤ D i j)
(hD_symm : ∀ i j, D i j = D j i)
(hD_zero : ∀ i j, D i j = 0 ↔ i = j)
(hD_tri : ∀ i j k, D i k ≤ D i j + D j k)
(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) :
CompOT.Assignment.frob (powCost D p) (glue b P Q) ^ (1 / p) ≤
CompOT.Assignment.frob (powCost D p) P ^ (1 / p) + CompOT.Assignment.frob (powCost D p) Q ^ (1 / p) := by sorry
end CompOT.Metric
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), proof of Proposition 2.2, pp. 378–379
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.