§6.5, p. 47 — the covariance-selection Z-update is elementwise soft thresholding
ProvedBoydADMM.L1.covsel_Z_updateadmmcovariance-selectionp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1soft-thresholding
Let , and . The matrix with entries
is the unique minimizer over all of
where and is scalar soft thresholding.
With and this is the Z-update of ADMM for sparse inverse covariance selection.
Formalization Note The regularization weight is called lam. The book takes ; the statement is made for , which contains it. The minimization is over all real matrices; when and are symmetric the minimizer is symmetric, so minimizing over symmetric matrices gives the same update.
Preamble
import Mathlib import Definitions.Def_BoydADMM_L1_Basic import Definitions.Def_BoydADMM_L1_CovSel open Matrix
Formal statement
namespace BoydADMM.L1
/-- §6.5, p. 47: for `λ ≥ 0` (called `lam`) and `ρ > 0`, the matrix with entries
`S_{λ/ρ}(X_ij + U_ij)` is the unique minimizer of `λ‖Z‖₁ + (ρ/2)‖X − Z + U‖_F²` over all real
`n × n` matrices `Z`. -/
theorem covsel_Z_update {n : ℕ} (lam ρ : ℝ) (hlam : 0 ≤ lam) (hρ : 0 < ρ)
(X U : Matrix (Fin n) (Fin n) ℝ) :
IsUniqueMinimizerOn (covselZObjective lam ρ X U) Set.univ
(Matrix.of fun i j => BoydADMM.Prox.softThreshold (lam / ρ) (X i j + U i j)) := 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. 47, §6.5 (Z-minimization step); objective on p. 46
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.