Lemma 1 — there is e > 0 with Fₘ(ȳ) ≦ e Fₘ(y) for every y and every subset S of the rows
ProvedHoffmanBound.ErrorBound.lemma1compactnesslinear-inequalitiesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a positive homogeneous function on in the sense of (3). Then there exists such that for every and every subset of the half spaces (rows) of (1),
The constant is uniform in and . It lets the bound obtained on the active rows pass back to the full residual ; for the three norms of Section 3, .
Preamble
import Mathlib import Definitions.Def_HoffmanBound_ErrorBound_Model
Formal statement
namespace HoffmanBound.ErrorBound
/-- Hoffman 1952, p. 263, Lemma 1. If `F_m` satisfies (3), there is `e > 0` such that for every
`y` and every subset `S` of the rows, `F_m(ȳ) ≤ e F_m(y)`, where `ȳ` keeps the coordinates of `y`
in `S` and replaces the others by `0`. -/
theorem lemma1 {m : ℕ} (Fm : (Fin m → ℝ) → ℝ) (hFm : IsPosHomogeneous Fm) :
∃ e : ℝ, 0 < e ∧ ∀ (y : Fin m → ℝ) (S : Finset (Fin m)), Fm (restrictVec S y) ≤ e * Fm y := by sorry
end HoffmanBound.ErrorBound
Source
Hoffman, On Approximate Solutions of Systems of Linear Inequalities, J. Res. Nat. Bur. Standards 49 (1952), p. 263 (PDF p. 1), Lemma 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.