Eqs. (36)–(37) — gives column error at most
ProvedGlobalSinkhorn.column_error_of_potentialdoubly-stochasticmatrix-scalingp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1sinkhorn-knoppspectral-gap
Let , let be a nonnegative doubly stochastic matrix, let , and let . If
then every column sum of is within of :
Combined with and the decay of , this gives the columnwise error bound (21) of Theorem 3.1.
Differences from the source:
- encoding: indices [n] = {1,…,n} → Fin n (0-based); reason: Lean convention; same instances
- encoding: S nonnegative and doubly stochastic → S ∈ doublyStochastic ℝ (Fin n) (entries ≥ 0, all row and column sums 1); reason: Mathlib's doubly stochastic matrices are exactly the paper's
- encoding: M(w), F(w) defined with (Sw)⁻¹ and [Sᵀ(Sw)⁻¹]⁻¹ for w > 0 → Lean's total inverse in Mw, Fw; reason: for w > 0 and doubly stochastic S every inverted entry is positive (p.15), so the junk value 0 is never used
- encoding: ⟨v⟩ = (1/n) Σ_j v_j and componentwise powers/reciprocals → avg v = (Σ_j v j)/n, (w j)⁻¹, w j ^ 2; reason: notation of p.13 written out
- generalization: w = w_t, the t-th iterate, rescaled so that ⟨w⟩ = 1 → every w > 0 with Φ(w) ≤ ε²/(16n³); reason: the page's argument uses only Φ(w) ≤ ε²/(16n³), and M(w), Φ(w) are invariant under rescaling w; the iterate w_t is a special case
Preamble
import Mathlib import Definitions.Def_GlobalSinkhorn_potential import Definitions.Def_GlobalSinkhorn_Mw open Matrix
Formal statement
namespace GlobalSinkhorn
/-- If `Φ(w) ≤ ε²/(16n³)`, then every column sum of `M(w)` is within `ε/n` of `1`.
He, Global Sinkhorn Convergence and Spectral Stability of Matrix Scaling, manuscript (STOC 2027 submission, sha256 b452ef13…34ad), proof of Theorem 3.1, Eqs. (36)–(37), pp.20–21. -/
theorem column_error_of_potential {n : ℕ} (hn : 2 ≤ n) (S : Matrix (Fin n) (Fin n) ℝ)
(hS : S ∈ doublyStochastic ℝ (Fin n)) (w : Fin n → ℝ) (hw : ∀ j, 0 < w j)
(ε : ℝ) (hε : 0 < ε) (hε1 : ε ≤ 1)
(hΦ : potential w ≤ ε ^ 2 / (16 * (n : ℝ) ^ 3)) (j : Fin n) :
|∑ i, Mw S w i j - 1| ≤ ε / n := by sorry
end GlobalSinkhorn
Source
He, Global Sinkhorn Convergence and Spectral Stability of Matrix Scaling, manuscript (STOC 2027 submission, sha256 b452ef1311fa669023fddd0c074df8a61571bf17b5712615c09d1495a34034ad), proof of Theorem 3.1, Eqs. (36)–(37), pp.20–21
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.