Proof of Proposition 4.1, relations (i)–(iii) — ,
ProvedPALM.ProxNMF.facts_i_ii_iiinonconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sparsity
Fix and let , , , and componentwise. Then for every :
- if and only if for all .
These identities convert the constrained proximal problem of Proposition 4.1 into a hard-thresholding problem for .
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
/-- Relations (i)–(iii) in the proof of Proposition 4.1 (pp. 28–29): for every `X` (with `U` fixed),
(i) `‖X‖²_F = ‖X‖²_+ + ‖X‖²_−`, (ii) `‖X − U‖²_+ + ‖X‖²_− = ‖X − P_+(U)‖²_F`,
(iii) `‖X‖²_− = 0 ⇔ X_ij = 0` for all `(i, j) ∈ I⁻`. -/
theorem facts_i_ii_iii {m n : ℕ} (U X : Matrix (Fin m) (Fin n) ℝ) :
frobInner X X = normSqPlus U X + normSqMinus U X ∧
normSqPlus U (X - U) + normSqMinus U X = frobInner (X - Pplus U) (X - Pplus U) ∧
(normSqMinus U X = 0 ↔ ∀ p ∈ Iminus U, X p.1 p.2 = 0) := 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), pp. 28–29, §4.2, proof of Proposition 4.1, relations (i)–(iii)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.