Lemma 4, p. 9 — bounded ‖s‖^λ_F implies the R-linear rate ‖s(k)‖_F ≤ Uλᵏ
ProvedDIGing.Undir.lemma_4ergodic-normlinear-convergencep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and let be matrices. If , then
so converges to at a global R-linear (geometric) rate .
This turns the bound produced by the small gain theorem into the convergence rate claimed in Theorem 10.
Formalization Note. The bound on the supremum is stated pointwise in .
Preamble
import Mathlib import Definitions.Def_DIGing_Undir_Common
Formal statement
namespace DIGing.Undir
theorem lemma_4 {n p : ℕ} (s : ℕ → Stack n p) (lam : ℝ) (hlam0 : 0 < lam) (hlam1 : lam < 1)
(U : ℝ) (hU : ∀ k : ℕ, frob (s k) / lam ^ k ≤ U) :
∀ k : ℕ, frob (s k) ≤ U * lam ^ k := by sorry
end DIGing.Undir
Source
Nedić, Olshevsky & Shi, arXiv:1607.03218v3, Lemma 4, p. 9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.