Theorem 2.2, p. 8 — for small p > 0 the Lp-L1 solution set lies in the L0-L1 solution set and is constant on (0, p̄]
ProvedSparseLpLq.SmallP.theorem_2_2cardinality-minimizationlp-minimizationnonconvex-optimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-optimization
Let , and satisfy the paper's blanket assumptions for : the feasible set is nonempty and . For let be the set of optimal solutions of
where for and is the number of nonzero entries. Then:
- there exists such that
- moreover, for this there exists such that
No condition on (such as a restricted isometry or null space property) is assumed. The first clause says that solving the nonconvex problem with any sufficiently small yields a sparsest feasible point; the second says that the solution set stops changing once is small enough.
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_SparseLpLq_SmallP_Setting open scoped ENNReal Matrix
Formal statement
namespace SparseLpLq.SmallP
theorem theorem_2_2 {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (σ : ℝ)
(hσ : 0 ≤ σ) (hfeas : (FEA A b σ 1).Nonempty) (hb : σ < qNorm 1 b) :
∃ pstar ∈ Set.Ioc (0 : ℝ) 1,
(∀ p ∈ Set.Ioo 0 pstar, SOL A b σ p 1 ⊆ SOL A b σ 0 1) ∧
∃ pbar ∈ Set.Ioo 0 pstar, ∀ p ∈ Set.Ioc 0 pbar, SOL A b σ p 1 = SOL A b σ pbar 1 := by sorry
end SparseLpLq.SmallP
Source
Yang, Chen & Xiang, Sparse solutions of a class of constrained optimization problems, arXiv:1907.00880v5, p. 8, Theorem 2.2; proof pp. 8–9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.