Lemma 2.1 — for f_LI(x) = ‖Ax − b‖² with A s-regular, problem (P) has finitely many BF points
ProvedSparseNLO.IHT.lemma_2_1least-squaresoptimality-conditionsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-optimization
Let , let be an -regular matrix (every of its columns are linearly independent) and let . Take ,
Then the set of basic feasible (BF) points of problem (P),
is finite.
Finiteness of the BF points is what lets the proof of Theorem 3.2 separate the candidate limits of the IHT method by a positive distance.
Formalization Note is Matrix.toEuclideanLin A x and is the Euclidean norm on EuclideanSpace ℝ (Fin m). Assumption 1 holds automatically for and is not stated.
Preamble
import Mathlib import Definitions.Def_SparseNLO_IHT_Setting open Filter Topology
Formal statement
namespace SparseNLO.IHT
/-- Lemma 2.1 (p. 6). Let `f = f_LI`, `f_LI(x) = ‖Ax − b‖²`, where `A ∈ ℝ^{m×n}` is `s`-regular and
`b ∈ ℝ^m`. Then the number of BF points of problem (P) is finite. -/
theorem lemma_2_1 {m n s : ℕ} (hs : 0 < s) (hsn : s < n)
(A : Matrix (Fin m) (Fin n) ℝ) (b : EuclideanSpace ℝ (Fin m)) (hA : IsSRegular s A) :
{x : EuclideanSpace ℝ (Fin n) | SparseNLO.CWOpt.IsBF (fLI A b) s x}.Finite := by sorry
end SparseNLO.IHT
Source
Beck, Eldar, Sparsity Constrained Nonlinear Optimization: Optimality Conditions and Algorithms, SIAM J. Optim. (2013), doi:10.1137/120869778 (source: arXiv:1203.4580v1), p. 6, Lemma 2.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.