§4.4.3, p. 32 — the scalar x_i-update for λ|x_i| is x_i⁺ = S_{λ/ρ}(v_i)
ProvedBoydADMM.Prox.scalar_soft_thresholdl1-regularizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1proximal-operatorsoft-thresholding
Let , and . The scalar problem
has the unique solution
That is, minimizes over if and only if .
This is the scalar update that component separability (§4.4.2) reduces the -regularized -update to.
Formalization Note The book writes "the solution"; the objective is strictly convex, so we state that is a minimizer and the only one, as an equivalence. is written lam because λ is a Lean keyword.
Preamble
import Mathlib import Definitions.Def_BoydADMM_Prox_Basic open Matrix
Formal statement
namespace BoydADMM.Prox
theorem scalar_soft_threshold (lam ρ : ℝ) (hlam : 0 < lam) (hρ : 0 < ρ) (a t : ℝ) :
(∀ s : ℝ, lam * |t| + (ρ / 2) * (t - a) ^ 2 ≤ lam * |s| + (ρ / 2) * (s - a) ^ 2) ↔
t = softThreshold (lam / ρ) a := by sorry
end BoydADMM.Prox
Source
Boyd, Parikh, Chu, Peleato, Eckstein, Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, Found. Trends Mach. Learn. 3(1) (2011), p. 32, §4.4.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.