§6.1.1, p. 40 — the Huber-fitting z-update is ,
ProvedBoydADMM.L1.huber_z_updateadmmhuberp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1proximal-operator
Let , , and , and put . The vector with components
is the unique minimizer over of
where is the Huber penalty with transition at level and is soft thresholding applied elementwise.
With and this is the z-update of scaled-form ADMM for Huber fitting, minimize , written with the constraint : the proximity operator of the Huber function.
Formalization Note Vectors are EuclideanSpace ℝ (Fin m) and acts by Matrix.toEuclideanLin. The formula is applied componentwise, as the book's is.
Preamble
import Mathlib import Definitions.Def_BoydADMM_L1_Basic open Matrix
Formal statement
namespace BoydADMM.L1
/-- §6.1.1, p. 40: for `ρ > 0`, with `v = Ax − b + u`, the vector with components
`(ρ/(1+ρ)) v_i + (1/(1+ρ)) S_{1+1/ρ}(v_i)` is the unique minimizer of
`g^hub(z) + (ρ/2)‖Ax − z − b + u‖₂²` over `z ∈ ℝᵐ`. -/
theorem huber_z_update {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b u : EuclideanSpace ℝ (Fin m))
(x : EuclideanSpace ℝ (Fin n)) (ρ : ℝ) (hρ : 0 < ρ) :
IsUniqueMinimizerOn
(fun z : EuclideanSpace ℝ (Fin m) =>
huberVec z + (ρ / 2) * ‖Matrix.toEuclideanLin A x - z - b + u‖ ^ 2) Set.univ
(WithLp.toLp 2 fun i =>
ρ / (1 + ρ) * (Matrix.toEuclideanLin A x - b + u) i +
1 / (1 + ρ) * BoydADMM.Prox.softThreshold (1 + 1 / ρ) ((Matrix.toEuclideanLin A x - b + u) i)) := by sorry
end BoydADMM.L1
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. 40, §6.1.1 (Huber fitting); ADMM form from §6.1, p. 39
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.