Proposition 3.3, p. 7 — on K-sparse vectors the induced norm ‖·‖c equals ‖·‖s
ProvedPermInvConvex.Sparsity.proposition_3_3cardinality-constraintgaugep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a symmetric gauge function on , , and the gauge of . If has , then
The two norms therefore agree on the sparse vectors, which is how the paper evaluates for the -sparse vector .
Formalization Note is the standing assumption of §3 (p. 6).
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 proposition_3_3 {n : ℕ} (ns : (Fin n → ℝ) → ℝ) (hns : IsSymmetricGauge ns)
(K : ℕ) (hK : 1 < K) (hKn : K < n) (x : Fin n → ℝ) (hx : card x ≤ K) :
normC ns K x = ns 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, Proposition 3.3 (standing assumption 1 < K < n, p. 6)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.