Lemma 3.1, p. 7 — permutation-invariant norms are monotone under majorization
ProvedPermInvConvex.Sparsity.lemma_3_1majorizationnormp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1schur-convexity
Let be a permutation-invariant norm on and let with ( majorizes ). Then
The paper quotes this from the literature (its reference [20]); it is the step that turns a majorization relation between vectors into an inequality between their norms, used in the proofs of Theorems 3.1 and 3.2.
Formalization Note is a function (Fin n → ℝ) → ℝ with the norm and permutation-invariance axioms (no sign invariance is required). Majorization is stated through sums of the largest entries.
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 lemma_3_1 {n : ℕ} (f : (Fin n → ℝ) → ℝ) (hf : IsPermInvNorm f)
(x y : Fin n → ℝ) (hxy : Majorizes x y) :
f y ≤ f x := by sorry
end PermInvConvex.Sparsity
Source
Kim, Tawarmalani, Richard, Convexification of Permutation-Invariant Sets and an Application to Sparse PCA, arXiv:1910.02573v2, p. 7, Lemma 3.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.