Proposition 3 — the violation set V of Algorithm 2 is a correlation threshold test
ProvedL0BnB.DualGap.proposition_3active-setoptimality-conditionsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-regression
Let have columns of unit norm, , , and let with residual . Then the set of Step 2 of Algorithm 2 (the coordinates at which is not a minimizer of over ) can be written as
where if and if .
The proposition turns the optimality check of Algorithm 2 into a test on correlations with the residual. It is what makes usable in the dual-bound analysis.
Formalization Note The unit-norm assumption on the columns of is the standing assumption of Section 3 of the paper; the unit norm of is not needed here and is not assumed. is an arbitrary vector: the identity does not use that it comes from Algorithm 2.
Preamble
import Mathlib import Definitions.Def_L0BnB_DualGap_Setup
Formal statement
namespace L0BnB.DualGap
/-- Proposition 3, p. 12: with `r̂ = y − Xβ̂` and unit-norm columns of `X`,
`V = {i ∈ Supp(β̂)ᶜ | |⟨r̂, Xᵢ⟩| > c(λ₀, λ₂, M)}` (17). -/
theorem proposition_3 {n p : ℕ} (X : Matrix (Fin n) (Fin p) ℝ) (y : Fin n → ℝ)
(lam0 lam2 M : ℝ) (hlam0 : 0 < lam0) (hlam2 : 0 < lam2) (hM : 0 < M)
(hX : ∀ i, ∑ r, X r i ^ 2 = 1) (βhat : Fin p → ℝ) :
Vset X y lam0 lam2 M βhat =
Finset.univ.filter
(fun i => βhat i = 0 ∧ cThr lam0 lam2 M < |colInner X (resid X y βhat) i|) := by sorry
end L0BnB.DualGap
Source
Hazimeh, Mazumder, Saab, Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization, arXiv:2004.06152v2, p. 12, Proposition 3, (17); proof p. 30; standing assumption p. 9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.