§9.1 — projection onto a cardinality-constrained set
ProvedBoydADMM.Nonconvex.cardinality_projectionhard-thresholdingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1projectionsparsity
Let and . Choose an index set of size such that whenever and . Let on and elsewhere. Then has at most nonzero entries and
Thus keeping any largest-magnitude coordinates gives a Euclidean projection onto the sparsity set.
Formalization Note When , all coordinates are retained. Tied magnitudes can produce several nearest points; this theorem accepts every eligible and asserts nearest-point status, not uniqueness.
Preamble
import Mathlib import Definitions.Def_BoydADMM_Nonconvex_ProjectionBasics
Formal statement
namespace BoydADMM.Nonconvex
/-- §9.1, p. 74: any choice of the `min c n` largest-magnitude coordinates
gives a nearest point of the cardinality-constrained set. -/
theorem cardinality_projection {n : ℕ} (v : Fin n → ℝ) (c : ℕ)
(I : Finset (Fin n))
(hcard : I.card = min c n)
(hlargest : ∀ i ∈ I, ∀ j ∉ I, |v j| ≤ |v i|) :
restrictTo I v ∈ sparseSet c ∧
∀ x ∈ sparseSet c, sqDist (restrictTo I v) v ≤ sqDist x v := by sorry
end BoydADMM.Nonconvex
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. 74, §9.1, Cardinality bullet
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.