Theorem 5 — robust regression has a solution supported on if some allowable perturbation of the features outside makes them irrelevant
ProvedRobustRegLasso.Sparsity.theorem_5_sparse_solutionLet , radii , and , the feature-wise uncoupled uncertainty set. Let , and write , where agrees with on the features in and is zero elsewhere.
Suppose there is a perturbation of the features in (that is, zero on every feature in ) such that the robust regression problem
has a solution supported on . Then the robust regression problem
has a solution supported on : some optimal solution has for all .
In words, a robust regression has an optimal solution supported on if some allowable perturbation of the features outside makes them irrelevant. This connects robustness to sparsity, and is the tool from which the paper derives its incoherence-type criterion (Theorem 6).
Formalization Note "Has a solution supported on " is the existence of a minimizer of the robust objective (the EReal supremum over the set) with zero entries off . The perturbation is encoded as an element of that vanishes on . The radii are the paper's standing convention. The paper writes on p. 8; features are indexed by .
import Mathlib import Definitions.Def_RobustRegLasso_Sparsity_Basic
namespace RobustRegLasso.Sparsity
theorem theorem_5_sparse_solution {n m : ℕ} (a : Fin m → EuclideanSpace ℝ (Fin n))
(b : EuclideanSpace ℝ (Fin n)) (c : Fin m → ℝ) (hc : ∀ i, 0 ≤ c i) (I : Finset (Fin m))
(h : ∃ δTilde ∈ (RobustRegLasso.FeatureWise.uncertaintySet c : Set (Fin m → EuclideanSpace ℝ (Fin n))),
(∀ i, i ∈ I → δTilde i = 0) ∧
HasSolutionSupportedOn (a + δTilde) b (restrictedSet c I) I) :
HasSolutionSupportedOn a b (RobustRegLasso.FeatureWise.uncertaintySet c) I := by sorry
end RobustRegLasso.Sparsity
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.