§6.2, p. 41 — the basis-pursuit x-update is
ProvedBoydADMM.L1.basis_pursuit_x_updateadmmbasis-pursuitp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1projection
Let with invertible, , and . Then
is the Euclidean projection of onto the affine set : , and for every other with .
With and this is the x-update of ADMM for basis pursuit, minimize subject to : a minimum Euclidean norm problem with linear constraints, in closed form.
Formalization Note The book assumes and uses without stating that it exists; the statement assumes ( has full row rank), which is what the formula needs. Uniqueness of the nearest point is part of the conclusion. Vectors are EuclideanSpace, matrices act by Matrix.toEuclideanLin.
Preamble
import Mathlib import Definitions.Def_BoydADMM_L1_Basic open Matrix
Formal statement
namespace BoydADMM.L1
/-- §6.2, p. 41: if `AAᵀ` is invertible, then
`(I − Aᵀ(AAᵀ)⁻¹A)(z − u) + Aᵀ(AAᵀ)⁻¹b` is the Euclidean projection `Π(z − u)` of `z − u` onto
`{x ∈ ℝⁿ | Ax = b}`: the unique point of that set nearest to `z − u`. -/
theorem basis_pursuit_x_update {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ)
(b : EuclideanSpace ℝ (Fin m)) (hA : (A * Aᵀ).det ≠ 0) (z u : EuclideanSpace ℝ (Fin n)) :
IsUniqueMinimizerOn (fun x : EuclideanSpace ℝ (Fin n) => ‖x - (z - u)‖)
{x | Matrix.toEuclideanLin A x = b}
(Matrix.toEuclideanLin (1 - Aᵀ * (A * Aᵀ)⁻¹ * A) (z - u) +
Matrix.toEuclideanLin (Aᵀ * (A * Aᵀ)⁻¹) b) := 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. 41, §6.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.