Proof of Proposition 3.4, p. 407 — P ± tE stays in U(a, b) for a small step t > 0
ProvedCompOT.Vertices.prop_3_4_perturbation_feasibleextreme-pointoptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1transportation-polytope
Let , be the book's histograms and . Let have zero row sums and zero column sums, and , and be supported on the support of : implies . Then there is such that
Since , a nonzero such shows that is not an extremal point of . This is the feasibility half of the proof of Proposition 3.4.
Formalization Note The simplex hypotheses are the book's standing notation (p. 360). The step plays the role of the book's "elementary amount of flow" .
Preamble
import Mathlib import Definitions.Def_CompOT_Vertices_Defs
Formal statement
namespace CompOT.Vertices
/-- Proof of Proposition 3.4, p. 407: for histograms `a ∈ Σₙ`, `b ∈ Σₘ`, a perturbation matrix `E` with zero row sums
(`E 𝟙_m = 0_n`), zero column sums (`Eᵀ 𝟙_n = 0_m`) and supported on the support of `P`
can be added to and subtracted from a coupling `P ∈ U(a, b)` with a small enough positive
step `t` (the book's "elementary amount of flow" `ε`), and both `Q = P + tE` and
`R = P − tE` stay in `U(a, b)`. -/
theorem prop_3_4_perturbation_feasible {n m : ℕ} (a : Fin n → ℝ) (b : Fin m → ℝ)
(P E : Matrix (Fin n) (Fin m) ℝ)
(ha : a ∈ stdSimplex ℝ (Fin n)) (hb : b ∈ stdSimplex ℝ (Fin m))
(hP : P ∈ CompOT.Assignment.couplings a b)
(hrow : ∀ i, ∑ j, E i j = 0) (hcol : ∀ j, ∑ i, E i j = 0)
(hsupp : ∀ i j, E i j ≠ 0 → 0 < P i j) :
∃ t : ℝ, 0 < t ∧ P + t • E ∈ CompOT.Assignment.couplings a b ∧ P - t • E ∈ CompOT.Assignment.couplings a b := by sorry
end CompOT.Vertices
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), §3.4.1, proof of Proposition 3.4, p. 407 (Q = P + E and R = P − E are feasible)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.