Proposition 4.1 (Proximal map formula) — for
ProvedPALM.ProxNMF.proposition_4_1Let , let be a natural number, and let , the indicator of the nonnegative matrices with at most nonzero entries. Then
where is the proximal map (2.2) with , is the hard-thresholding operator of Definition 4.1, and componentwise. All three sides are sets, and both equalities are equalities of sets.
This formula is what makes PALM implementable for sparse nonnegative matrix factorization: the proximal step for the nonconvex constraint reduces to clipping the negative entries of and then keeping largest entries.
Formalization Note Matrices are Matrix (Fin m) (Fin n) ℝ. takes values in EReal, so membership in is the inequality in EReal for every . No restriction is placed on : and are included.
import Mathlib import Definitions.Def_CaiCandesShen_ProximalLimit_Basic import Definitions.Def_PALM_ProxNMF_Setting open CaiCandesShen.ProximalLimit PALM.ProxNMF
namespace PALM.ProxNMF
/-- Proposition 4.1 (Proximal map formula), p. 28: for `f := δ_{X≥0} + δ_{‖X‖₀≤s}`,
`prox^f_1(U) = argmin {½‖X − U‖²_F : X ≥ 0, ‖X‖₀ ≤ s} = T_s(P_+(U))`, as sets. -/
theorem proposition_4_1 {m n : ℕ} (s : ℕ) (U : Matrix (Fin m) (Fin n) ℝ) :
proxSet (f s) 1 U =
argminOn (fun X => 1 / 2 * frobInner (X - U) (X - U))
{X | X ∈ NonnegSet m n ∧ l0 X ≤ s} ∧
argminOn (fun X => 1 / 2 * frobInner (X - U) (X - U))
{X | X ∈ NonnegSet m n ∧ l0 X ≤ s} =
Ts s (Pplus U) := by sorry
end PALM.ProxNMF
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.