Lemma A.1, Appendix A.2, p. 16 — a vector at least as far from x_c moves away from x_c on its support
ProvedMConvexL1.SD.lemma_A_1l1-distancem-convex-functionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be a finite set and with and . If , then
(or both). The lemma is a purely metric fact about the norm on the hyperplane ; it selects the index at which the exchange property is applied in Lemma A.3 and in the proof of Theorem 4.1.
Differences from the source:
- generalization: N = {1, …, n} with n ≥ 2 (§2, p. 4) → an arbitrary finite type V with decidable equality (any cardinality, including 0 and 1); reason: taking V = Fin n with n ≥ 2 gives the paper's setting; for |V| ≤ 1 two distinct vectors cannot have equal sums, so the hypotheses cannot hold and the statement is vacuously true
- encoding: ‖x − y‖₁ = Σ |x(i) − y(i)| → L1Dist x y = Σ_v |x v − y v| as a natural number; reason: the norm is a nonnegative integer; same values
Preamble
import Mathlib import Definitions.Def_MConvexL1_SD_Basic import Definitions.Def_DiscreteConvex_MConvexFunctions_MExchangeAxiom import Definitions.Def_DiscreteConvex_MConvexFunctions_ArgMin open DiscreteConvex.MConvexFunctions DiscreteConvex.Algorithms
Formal statement
namespace MConvexL1.SD
theorem lemma_A_1 {V : Type*} [Fintype V] [DecidableEq V] (xc y yt : V → ℤ) (hne : y ≠ yt)
(hsum : ∑ v, y v = ∑ v, yt v) (hdist : L1Dist y xc ≤ L1Dist yt xc) :
(∃ i ∈ SuppPos yt y, xc i < yt i) ∨ (∃ j ∈ SuppNeg yt y, yt j < xc j) := by sorry
end MConvexL1.SD
Source
Shioura, M-convex Function Minimization Under L1-Distance Constraint, arXiv:1809.03126v3, Appendix A.2, p. 16, Lemma A.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.