§6.5, p. 47 — the covariance-selection X-update is
ProvedBoydADMM.L1.covsel_X_updateLet with and symmetric, and let . Let with and satisfy
Put
Then is symmetric positive definite, and it is the unique minimizer over the symmetric positive definite matrices of
With and this is the X-update of ADMM for sparse inverse covariance selection, minimize : the only update of the chapter that is neither a linear solve nor a thresholding, it costs one symmetric eigenvalue decomposition.
Formalization Note The book's eigenvalues are called . The statement holds for every orthogonal and diagonal factor with , not just one chosen by Mathlib. The symmetry of (an empirical covariance ) and of (the ADMM iterates are symmetric) is an explicit hypothesis; is not required to be positive semidefinite. The minimization is over Matrix.PosDef, the domain of (p. 46); singular matrices are not competitors. is the sum of squared entries.
import Mathlib import Definitions.Def_BoydADMM_L1_Basic import Definitions.Def_BoydADMM_L1_CovSel open Matrix
namespace BoydADMM.L1
/-- §6.5, p. 47 (the goal): let `S` and `Z − U` be symmetric, `ρ > 0`, and
`ρ(Z − U) − S = Q diag(μ) Qᵀ` with `QᵀQ = QQᵀ = I`. Then `X = Q X̃ Qᵀ`,
`X̃_ii = (μ_i + √(μ_i² + 4ρ))/(2ρ)`, is positive definite and is the unique minimizer of
`Tr(SX) − log det X + (ρ/2)‖X − Z + U‖_F²` over the positive definite matrices. -/
theorem covsel_X_update {n : ℕ} (S Z U Q : Matrix (Fin n) (Fin n) ℝ) (ρ : ℝ) (μ : Fin n → ℝ)
(hρ : 0 < ρ) (hS : S.IsSymm) (hZU : (Z - U).IsSymm)
(hQ₁ : Qᵀ * Q = 1) (hQ₂ : Q * Qᵀ = 1)
(hdecomp : ρ • (Z - U) - S = Q * Matrix.diagonal μ * Qᵀ) :
IsUniqueMinimizerOn (covselXObjective S Z U ρ) {X | X.PosDef} (covselX ρ Q μ) := by sorry
end BoydADMM.L1
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.