Proof of Proposition 4.1 — the constraint in problem (4.2) can be removed
ProvedPALM.ProxNMF.remove_nonnegnonconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sparsity
Fix and , with and as in the setting. Then
That is, dropping the nonnegativity constraint from problem (4.2) does not change its set of optimal solutions. Together with relations (ii) and (iii) this turns (4.2) into a hard-thresholding problem for without sign constraints.
Preamble
import Mathlib import Definitions.Def_CaiCandesShen_ProximalLimit_Basic import Definitions.Def_PALM_ProxNMF_Setting open CaiCandesShen.ProximalLimit PALM.ProxNMF
Formal statement
namespace PALM.ProxNMF
/-- Proof of Proposition 4.1 (p. 29): the constraint `X ≥ 0` in problem (4.2) can be removed
without affecting its set of optimal solutions. -/
theorem remove_nonneg {m n : ℕ} (s : ℕ) (U : Matrix (Fin m) (Fin n) ℝ) :
argminOn (fun X => normSqPlus U (X - U))
{X | (∀ p ∈ Iminus U, X p.1 p.2 = 0) ∧ X ∈ NonnegSet m n ∧ l0 X ≤ s} =
argminOn (fun X => normSqPlus U (X - U))
{X | (∀ p ∈ Iminus U, X p.1 p.2 = 0) ∧ l0 X ≤ s} := by sorry
end PALM.ProxNMF
Source
Bolte, Sabach, Teboulle, Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program. 146 (2014), doi:10.1007/s10107-013-0701-9 (source: author version), p. 29, §4.2, proof of Proposition 4.1 (unnumbered sentence after (4.2))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.