Theorem 4.2, p. 441 — Sinkhorn's iterates converge linearly in Hilbert's metric at rate λ(K)², with the a posteriori bounds (4.23) and (4.24)
ProvedCompOT.Sinkhorn.theorem_4_2Let , let , and have positive entries, and let with . Let be the iterates of Sinkhorn's algorithm
and let be vectors with positive entries solving , . Write for Hilbert's projective metric, and . Then:
- Linear rate (4.22). For every , , and for every , .
- Convergence. and as .
- A posteriori bounds (4.23). For every ,
and for every ,
- Couplings (4.24). For every ,
This is the global linear convergence of Sinkhorn's algorithm (Franklin and Lorenz, 1989): each iteration contracts the distance of the scalings to the solution by , and the marginal violations of the current coupling give computable stopping criteria.
Formalization Note (i) The book writes (4.22) as ; its proof yields the constants stated here, for and with exponent for . (ii) The book's "" is stated in its projective form (), which is what the proof establishes; scalings are only defined up to . (iii) As printed, the second inequality of (4.23) uses , which equals for every by (4.15), so its right side is and the printed inequality is false; the statement here uses the half-step coupling that the mirrored proof ("the second one being similar") produces. (iv) In (4.24), is taken as , which by Proposition 4.3 is the unique solution of (4.2); is the entrywise maximum norm. The book cites (4.24) to Franklin–Lorenz, Lemma 3, without proof. (v) The book's histograms lie in the probability simplex; only positivity and the existence of a positive solution (which forces ) are used. (vi) Iterates exist only for ; is unconstrained and only enters the limit statement. Indices are -based.
import Mathlib import Definitions.Def_CompOT_Sinkhorn_Defs
namespace CompOT.Sinkhorn
open Matrix Filter Topology
/-- Theorem 4.2 (Franklin–Lorenz), Remark 4.14, p. 441, with the explicit constants of
the book's proof in place of the `O(·)` of (4.22), and the second inequality of (4.23)
stated with the half-step coupling `diag(u^{(ℓ+1)}) K diag(v^{(ℓ)})` (as printed, with
`P^{(ℓ)}`, its right side is `0` for `ℓ ≥ 1`). Here `P⋆ = diag(u⋆) K diag(v⋆)`.
Iterates `u^{(ℓ)}` exist only for `ℓ ≥ 1`. -/
theorem theorem_4_2 {n m : ℕ} (hn : 0 < n) (hm : 0 < m)
(K : Matrix (Fin n) (Fin m) ℝ) (hK : ∀ i j, 0 < K i j)
(a : Fin n → ℝ) (ha : ∀ i, 0 < a i) (b : Fin m → ℝ) (hb : ∀ j, 0 < b j)
(u : ℕ → Fin n → ℝ) (v : ℕ → Fin m → ℝ) (hrun : IsSinkhornRun K a b u v)
(us : Fin n → ℝ) (vs : Fin m → ℝ) (hus : ∀ i, 0 < us i) (hvs : ∀ j, 0 < vs j)
(hsol : IsScalingSolution K a b us vs) :
-- (4.22), explicit: d_H(v^{(ℓ)}, v⋆) ≤ λ^{2ℓ} d_H(v^{(0)}, v⋆)
(∀ ℓ : ℕ, hilbertMetric (v ℓ) vs ≤ lam K ^ (2 * ℓ) * hilbertMetric (v 0) vs) ∧
-- (4.22), explicit: d_H(u^{(ℓ+1)}, u⋆) ≤ λ^{2ℓ+1} d_H(v^{(0)}, v⋆)
(∀ ℓ : ℕ, hilbertMetric (u (ℓ + 1)) us ≤
lam K ^ (2 * ℓ + 1) * hilbertMetric (v 0) vs) ∧
-- projective convergence (u^{(ℓ)}, v^{(ℓ)}) → (u⋆, v⋆) in d_H
Tendsto (fun ℓ => hilbertMetric (u ℓ) us) atTop (𝓝 0) ∧
Tendsto (fun ℓ => hilbertMetric (v ℓ) vs) atTop (𝓝 0) ∧
-- (4.23), first part as printed, for ℓ ≥ 1
(∀ ℓ : ℕ, 1 ≤ ℓ → hilbertMetric (u ℓ) us ≤
hilbertMetric (scaledCoupling (u ℓ) K (v ℓ) *ᵥ 1) a / (1 - lam K ^ 2)) ∧
-- (4.23), second part, with the half-step coupling diag(u^{(ℓ+1)}) K diag(v^{(ℓ)})
(∀ ℓ : ℕ, hilbertMetric (v ℓ) vs ≤
hilbertMetric ((scaledCoupling (u (ℓ + 1)) K (v ℓ))ᵀ *ᵥ 1) b / (1 - lam K ^ 2)) ∧
-- (4.24), for ℓ ≥ 1, with P⋆ = diag(u⋆) K diag(v⋆)
(∀ ℓ : ℕ, 1 ≤ ℓ →
(⨆ i, ⨆ j, |Real.log (scaledCoupling (u ℓ) K (v ℓ) i j) -
Real.log (scaledCoupling us K vs i j)|) ≤
hilbertMetric (u ℓ) us + hilbertMetric (v ℓ) vs) := by sorry
end CompOT.Sinkhorn
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.