Lemma A.2, Appendix A.2, p. 16 — an exchange step does not increase the sum of L1 distances to any point
ProvedMConvexL1.SD.lemma_A_2exchange-propertyl1-distancep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be a finite set, , and , where denotes the -th unit vector. Then
It says that the map satisfies the exchange inequality (M-EXC) with every admissible ; the paper uses it to combine exchanges of with the constraint of (MML1).
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 the sets supp⁺(x − y) and supp⁻(x − y) cannot both be nonempty, 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_2 {V : Type*} [Fintype V] [DecidableEq V] (x y z : V → ℤ) (i j : V)
(hi : i ∈ SuppPos x y) (hj : j ∈ SuppNeg x y) :
L1Dist x z + L1Dist y z ≥
L1Dist (fun w => x w - CharVec i w + CharVec j w) z +
L1Dist (fun w => y w + CharVec i w - CharVec j w) z := 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.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.