Proof of Proposition 4.1, (4.1) = (4.2) — the negative-index entries of a minimizer vanish
ProvedPALM.ProxNMF.eq_4_1_eq_4_2nonconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sparsity
Fix and , with and as in the setting. The two minimizer sets
and
are equal.
In the proof of Proposition 4.1, the objective of (4.1) is minus the constant , so this step shows that a nonnegative sparse projection of vanishes where is negative.
Formalization Note Both sides are sets of minimizers (possibly with several elements), not chosen points. The objective of (4.1) is written exactly as printed, without the constant .
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
/-- (4.1) = (4.2), proof of Proposition 4.1 (p. 29): the argmin of
`‖X − U‖²_+ + ‖X‖²_− − 2 ∑_{I⁻} X_ij U_ij` over `X ≥ 0, ‖X‖₀ ≤ s` equals the argmin of
`‖X − U‖²_+` over `X_ij = 0 ∀ (i, j) ∈ I⁻, X ≥ 0, ‖X‖₀ ≤ s`. -/
theorem eq_4_1_eq_4_2 {m n : ℕ} (s : ℕ) (U : Matrix (Fin m) (Fin n) ℝ) :
argminOn
(fun X => normSqPlus U (X - U) + normSqMinus U X
- 2 * ∑ p ∈ Iminus U, X p.1 p.2 * U p.1 p.2)
{X | X ∈ NonnegSet m n ∧ l0 X ≤ s} =
argminOn (fun X => normSqPlus U (X - U))
{X | (∀ p ∈ Iminus U, X p.1 p.2 = 0) ∧ X ∈ NonnegSet m n ∧ 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, (4.1)–(4.2)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.