Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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)

Proved
CompOT.Sinkhorn.theorem_4_2

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

hilbert-projective-metriclinear-convergenceoptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1sinkhorn

Let n,m≥1n, m \ge 1n,m≥1, let K∈Rn×mK \in \mathbb{R}^{n\times m}K∈Rn×m, a∈Rna \in \mathbb{R}^na∈Rn and b∈Rmb \in \mathbb{R}^mb∈Rm have positive entries, and let λ=λ(K)=η(K)−1η(K)+1\lambda = \lambda(K) = \frac{\sqrt{\eta(K)}-1}{\sqrt{\eta(K)}+1}λ=λ(K)=η(K)​+1η(K)​−1​ with η(K)=max⁡i,j,k,ℓKi,kKj,ℓKj,kKi,ℓ\eta(K) = \max_{i,j,k,\ell} \frac{K_{i,k}K_{j,\ell}}{K_{j,k}K_{i,\ell}}η(K)=maxi,j,k,ℓ​Kj,k​Ki,ℓ​Ki,k​Kj,ℓ​​. Let (u(ℓ),v(ℓ))(u^{(\ell)}, v^{(\ell)})(u(ℓ),v(ℓ)) be the iterates of Sinkhorn's algorithm

v(0)=1m,u(ℓ+1)=aKv(ℓ),v(ℓ+1)=bK⊤u(ℓ+1),v^{(0)} = \mathbb{1}_m,\qquad u^{(\ell+1)} = \frac{a}{Kv^{(\ell)}},\qquad v^{(\ell+1)} = \frac{b}{K^\top u^{(\ell+1)}},v(0)=1m​,u(ℓ+1)=Kv(ℓ)a​,v(ℓ+1)=K⊤u(ℓ+1)b​,

and let (u⋆,v⋆)(u^\star, v^\star)(u⋆,v⋆) be vectors with positive entries solving u⋆⊙(Kv⋆)=au^\star \odot (Kv^\star) = au⋆⊙(Kv⋆)=a, v⋆⊙(K⊤u⋆)=bv^\star \odot (K^\top u^\star) = bv⋆⊙(K⊤u⋆)=b. Write dHd_{\mathcal H}dH​ for Hilbert's projective metric, P(ℓ)=diag(u(ℓ))K diag(v(ℓ))P^{(\ell)} = \mathrm{diag}(u^{(\ell)})K\,\mathrm{diag}(v^{(\ell)})P(ℓ)=diag(u(ℓ))Kdiag(v(ℓ)) and P⋆=diag(u⋆)K diag(v⋆)P^\star = \mathrm{diag}(u^\star)K\,\mathrm{diag}(v^\star)P⋆=diag(u⋆)Kdiag(v⋆). Then:

  1. Linear rate (4.22). For every ℓ≥0\ell \ge 0ℓ≥0, dH(v(ℓ),v⋆)≤λ2ℓ dH(1m,v⋆)d_{\mathcal H}(v^{(\ell)}, v^\star) \le \lambda^{2\ell}\, d_{\mathcal H}(\mathbb{1}_m, v^\star)dH​(v(ℓ),v⋆)≤λ2ℓdH​(1m​,v⋆), and for every ℓ≥1\ell \ge 1ℓ≥1, dH(u(ℓ),u⋆)≤λ2ℓ−1 dH(1m,v⋆)d_{\mathcal H}(u^{(\ell)}, u^\star) \le \lambda^{2\ell-1}\, d_{\mathcal H}(\mathbb{1}_m, v^\star)dH​(u(ℓ),u⋆)≤λ2ℓ−1dH​(1m​,v⋆).
  2. Convergence. dH(u(ℓ),u⋆)→0d_{\mathcal H}(u^{(\ell)}, u^\star) \to 0dH​(u(ℓ),u⋆)→0 and dH(v(ℓ),v⋆)→0d_{\mathcal H}(v^{(\ell)}, v^\star) \to 0dH​(v(ℓ),v⋆)→0 as ℓ→∞\ell \to \inftyℓ→∞.
  3. A posteriori bounds (4.23). For every ℓ≥1\ell \ge 1ℓ≥1,
dH(u(ℓ),u⋆)≤dH(P(ℓ)1m, a)1−λ2,d_{\mathcal H}(u^{(\ell)}, u^\star) \le \frac{d_{\mathcal H}(P^{(\ell)}\mathbb{1}_m,\ a)}{1-\lambda^2},dH​(u(ℓ),u⋆)≤1−λ2dH​(P(ℓ)1m​, a)​,

and for every ℓ≥0\ell \ge 0ℓ≥0,

dH(v(ℓ),v⋆)≤dH((diag(u(ℓ+1))K diag(v(ℓ)))⊤1n, b)1−λ2.d_{\mathcal H}(v^{(\ell)}, v^\star) \le \frac{d_{\mathcal H}\big((\mathrm{diag}(u^{(\ell+1)})K\,\mathrm{diag}(v^{(\ell)}))^\top\mathbb{1}_n,\ b\big)}{1-\lambda^2}.dH​(v(ℓ),v⋆)≤1−λ2dH​((diag(u(ℓ+1))Kdiag(v(ℓ)))⊤1n​, b)​.
  1. Couplings (4.24). For every ℓ≥1\ell \ge 1ℓ≥1,
max⁡i,j∣log⁡Pi,j(ℓ)−log⁡Pi,j⋆∣≤dH(u(ℓ),u⋆)+dH(v(ℓ),v⋆).\max_{i,j} \big|\log P^{(\ell)}_{i,j} - \log P^\star_{i,j}\big| \le d_{\mathcal H}(u^{(\ell)}, u^\star) + d_{\mathcal H}(v^{(\ell)}, v^\star).i,jmax​​logPi,j(ℓ)​−logPi,j⋆​​≤dH​(u(ℓ),u⋆)+dH​(v(ℓ),v⋆).

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 λ(K)2<1\lambda(K)^2 < 1λ(K)2<1, and the marginal violations of the current coupling give computable stopping criteria.

Formalization Note (i) The book writes (4.22) as O(λ(K)2ℓ)O(\lambda(K)^{2\ell})O(λ(K)2ℓ); its proof yields the constants stated here, dH(v(0),v⋆)d_{\mathcal H}(v^{(0)}, v^\star)dH​(v(0),v⋆) for vvv and dH(v(0),v⋆)d_{\mathcal H}(v^{(0)}, v^\star)dH​(v(0),v⋆) with exponent 2ℓ−12\ell - 12ℓ−1 for uuu. (ii) The book's "(u(ℓ),v(ℓ))→(u⋆,v⋆)(u^{(\ell)}, v^{(\ell)}) \to (u^\star, v^\star)(u(ℓ),v(ℓ))→(u⋆,v⋆)" is stated in its projective form (dH→0d_{\mathcal H} \to 0dH​→0), which is what the proof establishes; scalings are only defined up to (ru,v/r)(ru, v/r)(ru,v/r). (iii) As printed, the second inequality of (4.23) uses P(ℓ),⊤1n=v(ℓ)⊙(K⊤u(ℓ))P^{(\ell),\top}\mathbb{1}_n = v^{(\ell)} \odot (K^\top u^{(\ell)})P(ℓ),⊤1n​=v(ℓ)⊙(K⊤u(ℓ)), which equals bbb for every ℓ≥1\ell \ge 1ℓ≥1 by (4.15), so its right side is 000 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), P⋆P^\starP⋆ is taken as diag(u⋆)K diag(v⋆)\mathrm{diag}(u^\star)K\,\mathrm{diag}(v^\star)diag(u⋆)Kdiag(v⋆), which by Proposition 4.3 is the unique solution of (4.2); ∥⋅∥∞\|\cdot\|_\infty∥⋅∥∞​ 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 (u⋆,v⋆)(u^\star, v^\star)(u⋆,v⋆) (which forces ∑iai=∑jbj\sum_i a_i = \sum_j b_j∑i​ai​=∑j​bj​) are used. (vi) Iterates u(ℓ)u^{(\ell)}u(ℓ) exist only for ℓ≥1\ell \ge 1ℓ≥1; u(0)u^{(0)}u(0) is unconstrained and only enters the limit statement. Indices are 000-based.

Preamble
import Mathlib
import Definitions.Def_CompOT_Sinkhorn_Defs
Formal statement
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
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), Remark 4.14, Theorem 4.2, (4.22)–(4.24), p. 441, and its proof, pp. 441–442
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me