Proposition 3.4, p. 8 — recursion for s(x), unimodality, u(x) ≥m |x|, and u(x)₁ = max{|x|[1], s(x)₁}
ProvedPermInvConvex.Sparsity.proposition_3_4closed-formmajorizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sparsity
Let , , and let , , and be as in (15). Then:
- for ,
- and ;
- ;
- .
Part 3 is the input to the inequality of Theorem 3.1, and Part 2 says the sequence is unimodal with its first minimum at .
Formalization Note with the paper's 1-based is decAbs x ⟨i - 1, _⟩, and is the Lean coordinate 0. Part 2 is stated as two monotonicity statements on the integer ranges and . No norm is involved; 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_4 {n : ℕ} (K : ℕ) (hK : 1 < K) (hKn : K < n) (x : Fin n → ℝ) :
(∀ (i : ℕ) (hi : 1 ≤ i) (hiK : i ≤ K - 1),
sVal K x (i + 1) - sVal K x i =
1 / ((K : ℝ) - i + 1) * (sVal K x (i + 1) - decAbs x ⟨i - 1, by omega⟩) ∧
sVal K x (i + 1) - sVal K x i =
1 / ((K : ℝ) - i) * (sVal K x i - decAbs x ⟨i - 1, by omega⟩)) ∧
((∀ i j : ℕ, 1 ≤ i → i ≤ j → j ≤ ix K x → sVal K x j ≤ sVal K x i) ∧
(∀ i j : ℕ, ix K x ≤ i → i ≤ j → j ≤ K → sVal K x i ≤ sVal K x j)) ∧
Majorizes (uVec K x) (absVec x) ∧
uVec K x ⟨0, by omega⟩ = max (decAbs x ⟨0, by omega⟩) (sVal K x 1) := by sorry
end PermInvConvex.Sparsity
Source
Kim, Tawarmalani, Richard, Convexification of Permutation-Invariant Sets and an Application to Sparse PCA, arXiv:1910.02573v2, p. 8, Proposition 3.4 (definitions on p. 7; standing assumption 1 < K < n, p. 6)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.