Proof of Theorem 3.2, p. 9 (Marshall–Olkin 5.A.9) — weak submajorization yields an intermediate majorized vector above y
ProvedPermInvConvex.Sparsity.weak_majorization_5A9majorizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1weak-majorization
Let with , that is, for . Then there exists with
The proof of the Sparsity Theorem cites this fact (5.A.9 of Marshall–Olkin–Arnold, Inequalities) with : it replaces a weakly majorizing feasible point of (11) by a vector it majorizes that dominates , so that Lemma 3.1 applies.
Formalization Note Stated for arbitrary real vectors, as in the cited source; is the pointwise order on Fin n → ℝ.
Preamble
import Mathlib import Definitions.Def_ModernConvex_Spectral_SDR import Definitions.Def_PermInvConvex_Sparsity_Majorization import Definitions.Def_PermInvConvex_Sparsity_Setting
Formal statement
namespace PermInvConvex.Sparsity
theorem weak_majorization_5A9 {n : ℕ} (u y : Fin n → ℝ) (h : WeakMajorizes u y) :
∃ u' : Fin n → ℝ, Majorizes u u' ∧ y ≤ u' := by sorry
end PermInvConvex.Sparsity
Source
Kim, Tawarmalani, Richard, Convexification of Permutation-Invariant Sets and an Application to Sparse PCA, arXiv:1910.02573v2, p. 9, proof of Theorem 3.2 (citing 5.A.9 of Marshall–Olkin–Arnold, Inequalities); also used on pp. 5–6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.