Theorem 3.2 (Sparsity Theorem), p. 9 — u(x) of (15) minimizes ‖u‖s over sparse sorted weak majorants of |x|; with p. 6, opt ≤ 1 iff x ∈ conv(N^K)
ProvedPermInvConvex.Sparsity.theorem_3_2Let be a symmetric gauge function (sign- and permutation-invariant norm) on , let be an integer with , and let . Consider
Then:
- (Sparsity Theorem) the closed-form vector of (15) is an optimal solution of (11): it is feasible, and for every feasible ;
- the optimal value of (11) is at most if and only if , where :
The theorem gives a membership test and a closed-form optimal solution for the convex hull of a cardinality-constrained norm ball, the feasible set of sparse principal component analysis when is the Euclidean norm.
Formalization Note Part 1 is Theorem 3.2 as printed on p. 9. Part 2 is the reading of the theorem given on p. 6 ("the optimal value of (11) is no more than 1 if and only if "); by Part 1 the optimal value equals , which is how it is written. is the standing assumption of §3 (p. 6). Lean vector index is the paper's ; is stated as for all (equivalent given the chain). is an arbitrary function satisfying the symmetric-gauge axioms, not Lean's sup norm.
import Mathlib import Definitions.Def_ModernConvex_Spectral_SDR import Definitions.Def_PermInvConvex_Sparsity_Majorization import Definitions.Def_PermInvConvex_Sparsity_Setting
namespace PermInvConvex.Sparsity
theorem theorem_3_2 {n : ℕ} (ns : (Fin n → ℝ) → ℝ) (hns : IsSymmetricGauge ns)
(K : ℕ) (hK : 1 < K) (hKn : K < n) (x : Fin n → ℝ) :
(uVec K x ∈ Feas11 K x ∧ ∀ u ∈ Feas11 K x, ns (uVec K x) ≤ ns u) ∧
(x ∈ convexHull ℝ (NK ns K) ↔ ns (uVec K x) ≤ 1) := by sorry
end PermInvConvex.Sparsity
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.