Lemma C.1, p. 24 — FEA(A,b,σ,1) = {x : UAx ≤ Ub + σ1}, U the matrix of all sign vectors
ProvedSparseLpLq.SmallP.lemma_c_1l1-normp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1polyhedrasparse-optimization
Let , and . Let be the set of all sign vectors and the matrix whose rows are these vectors, as in (C.1). Then the -feasible set is a polyhedron described by linear inequalities:
where . Row by row, the right-hand side is the set of with for every .
The lemma is what makes a convex polyhedron, so that its intersection with each orthant has finitely many extreme points; this finiteness underlies Proposition 2.1 and Theorem 2.2.
Formalization Note The rows of are quantified directly as all vectors with every entry equal to or , instead of an enumerated matrix.
Differences from the source:
- generalization: σ > 0 → 0 ≤ σ; reason: the identity holds verbatim at σ = 0 (both sides are {x : Ax = b}), and the paper's blanket assumption and Theorem 2.2 allow σ = 0; every instance with σ > 0 is an instance of the Lean statement
- encoding: the matrix U = [u₁, …, u_{2^m}]ᵀ and the vector inequality UAx ≤ Ub + σ1 → ∀ u with every uᵢ ∈ {1, −1}, u ⬝ᵥ (A x) ≤ u ⬝ᵥ b + σ; reason: the rows of U are exactly the sign vectors, and a vector inequality is the conjunction of its rows
Preamble
import Mathlib import Definitions.Def_SparseLpLq_SmallP_Setting open scoped ENNReal Matrix
Formal statement
namespace SparseLpLq.SmallP
theorem lemma_c_1 {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (σ : ℝ)
(hσ : 0 ≤ σ) :
FEA A b σ 1 =
{x | ∀ u : Fin m → ℝ, (∀ i, u i = 1 ∨ u i = -1) → u ⬝ᵥ (A *ᵥ x) ≤ u ⬝ᵥ b + σ} := by sorry
end SparseLpLq.SmallP
Source
Yang, Chen & Xiang, Sparse solutions of a class of constrained optimization problems, arXiv:1907.00880v5, p. 24, Lemma C.1 and (C.1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.