Theorem 4.1 (Birkhoff–Hopf), p. 440 — d_H(Kv, Kv′) ≤ λ(K) d_H(v, v′) with λ(K) < 1 for a positive matrix K
ProvedCompOT.Sinkhorn.theorem_4_1birkhoff-hopfhilbert-projective-metricoptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1perron-frobenius
Let and let have positive entries. Define
Then , and for all with positive entries,
where is Hilbert's projective metric.
This is the Birkhoff–Hopf theorem: a matrix with positive entries is a strict contraction of the positive cone for Hilbert's projective metric. It is the engine of the global linear convergence of Sinkhorn's algorithm (Theorem 4.2) and gives a quantitative Perron–Frobenius theorem (Remark 4.13).
Formalization Note The book quotes this theorem (Birkhoff 1957; Samelson et al. 1957) without proof.
Preamble
import Mathlib import Definitions.Def_CompOT_Sinkhorn_Defs
Formal statement
namespace CompOT.Sinkhorn
open Matrix
/-- Theorem 4.1 (Birkhoff–Hopf), p. 440: a matrix with positive entries is a strict
contraction for Hilbert's projective metric, with ratio
`λ(K) = (√η(K) − 1)/(√η(K) + 1) < 1`. -/
theorem theorem_4_1 {n m : ℕ} (hn : 0 < n) (hm : 0 < m)
(K : Matrix (Fin n) (Fin m) ℝ) (hK : ∀ i j, 0 < K i j)
(v v' : Fin m → ℝ) (hv : ∀ j, 0 < v j) (hv' : ∀ j, 0 < v' j) :
hilbertMetric (K *ᵥ v) (K *ᵥ v') ≤ lam K * hilbertMetric v v' ∧ lam K < 1 := by sorry
end CompOT.Sinkhorn
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), Remark 4.12, Theorem 4.1, p. 440
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.