Proof of Proposition 2.2, p. 377 — diag(a) is an optimal coupling of a with itself and W_p(a, a) = 0
ProvedCompOT.Metric.prop_2_2_diagoptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1wasserstein
Let be a distance on : symmetric, if and only if , and for all . Let and . Then the diagonal matrix is an optimal coupling in for the cost , its cost is zero, and
This is the first step of the definiteness part of Proposition 2.2: because has a null diagonal, the mass of can stay in place at no cost.
Formalization Note Indices are Fin n. The hypotheses (i)–(iii) of Proposition 2.2 and , are carried even where the step uses only part of them, so all items share one setting.
Preamble
import Mathlib import Definitions.Def_CompOT_Metric_Defs
Formal statement
namespace CompOT.Metric
open Matrix
/-- Proof of Proposition 2.2, p. 377: since `D^p` has a null diagonal, `W_p(a, a) = 0`,
with corresponding optimal transport matrix `P⋆ = diag(a)`. -/
theorem prop_2_2_diag {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 : Fin n → ℝ) (ha : a ∈ stdSimplex ℝ (Fin n)) :
CompOT.Assignment.IsOptimalCoupling (powCost D p) a a (Matrix.diagonal a) ∧
CompOT.Assignment.frob (powCost D p) (Matrix.diagonal a) = 0 ∧
W D p a a = 0 := by sorry
end CompOT.Metric
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), proof of Proposition 2.2, p. 377
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.