§8.3.2, p. 70 — with AᵢᵀAᵢ = Q diag(λ) Qᵀ, ‖(AᵢᵀAᵢ + νI)⁻¹Aᵢᵀv‖₂ = ‖diag(λ + ν1)⁻¹QᵀAᵢᵀv‖₂
ProvedBoydADMM.ModelFit.group_lasso_eigen_normadmmeigendecompositiongroup-lassop2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let and , and suppose
with orthogonal and (so is the vector of eigenvalues of , the squares of the singular values of ). Then for every
Once is cached, the right-hand side costs flops, which makes the one-parameter search over in the group-lasso update cheap.
Formalization Note The book calls the eigenvalue vector , clashing with the regularization weight; here it is . The book assumes tall () for the cost count; the identity does not need it, and no such hypothesis is imposed. That consists of eigenvalues, and that they are nonnegative, follows from the decomposition, so it is not assumed separately.
Preamble
import Mathlib import Definitions.Def_BoydADMM_ModelFit_Basic open Matrix
Formal statement
namespace BoydADMM.ModelFit
/-- §8.3.2, p. 70: if `AᵢᵀAᵢ = Q diag(μ) Qᵀ` with `Q` orthogonal, then for `ν > 0`
`‖(AᵢᵀAᵢ + νI)⁻¹Aᵢᵀv‖₂ = ‖diag(μ + ν1)⁻¹ Qᵀ Aᵢᵀ v‖₂`. (The book's eigenvalue vector `λ` is `μ`.) -/
theorem group_lasso_eigen_norm {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ)
(v : EuclideanSpace ℝ (Fin m)) (Q : Matrix (Fin n) (Fin n) ℝ)
(hQ : Q ∈ Matrix.orthogonalGroup (Fin n) ℝ) (μ : Fin n → ℝ)
(hdecomp : Aᵀ * A = Q * Matrix.diagonal μ * Qᵀ) (ν : ℝ) (hν : 0 < ν) :
‖ridgeSol A ν v‖ =
‖Matrix.toEuclideanLin ((Matrix.diagonal (fun j => μ j + ν))⁻¹ * Qᵀ * Aᵀ) v‖ := by sorry
end BoydADMM.ModelFit
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. 70, §8.3.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.