Proposition 2.2, p. 377 — for a distance matrix D and p ≥ 1, W_p = L_{D^p}^{1/p} is a distance on Σ_n
ProvedCompOT.Metric.proposition_2_2metricoptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1wasserstein
Let and let be a distance on , i.e.
- is symmetric;
- if and only if ;
- for all .
For histograms let , where is the optimal transport cost for the entrywise power . Then is a distance on : for all ,
Optimal transport thus lifts a ground distance on bins to a distance between histograms on those bins, the -Wasserstein distance.
Formalization Note Indices are Fin n (0-based); is Mathlib's stdSimplex ℝ (Fin n). The book's "positive" is read as nonnegativity; strict positivity for is the clause . The minimum is written as a real infimum over , which is nonempty and compact for . Powers are real powers with , . The book's is the hypothesis . For the simplex is empty and the statement holds vacuously, as in the book.
Preamble
import Mathlib import Definitions.Def_CompOT_Metric_Defs
Formal statement
namespace CompOT.Metric
open Matrix
/-- **Proposition 2.2** (p. 377). Let `D ∈ ℝ₊^{n×n}` be a distance on `⟦n⟧` (symmetric,
`D_{i,j} = 0 ↔ i = j`, triangle inequality) and `p ≥ 1`. Then `W_p(a, b) = L_{D^p}(a, b)^{1/p}`
(2.17) is a distance on `Σ_n`: symmetric, nonnegative, `W_p(a, b) = 0 ↔ a = b`, and it satisfies
the triangle inequality. -/
theorem proposition_2_2 {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 ∈ stdSimplex ℝ (Fin n), ∀ b ∈ stdSimplex ℝ (Fin n), ∀ c ∈ stdSimplex ℝ (Fin n),
W D p a b = W D p b a ∧
0 ≤ W D p a b ∧
(W D p a b = 0 ↔ a = b) ∧
W D p a c ≤ W D p a b + W D p b c := by sorry
end CompOT.Metric
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), Proposition 2.2 and (2.17), p. 377
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.