p. 38 โ (28) and (27) yield the threshold bound, hence ๐ โ ๐_s when ฮดโ = s/(2ep)
ProvedSubsetShrink.Events.F_subset_Egaussian-noisehigh-probability-eventsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-regression
Let have columns of unit Euclidean norm, let , , and . Then for every ,
and consequently the event (with this ) is contained in the event .
Together with the bound this gives , the first part of Theorem 1.
Formalization Note Events are sets of noise vectors (F, E of the definition file); enters through sortedSum.
Preamble
import Mathlib import Definitions.Def_SubsetShrink_Events_Model open MeasureTheory ProbabilityTheory
Formal statement
namespace SubsetShrink.Events
theorem F_subset_E {n p s : โ} (X : Matrix (Fin n) (Fin p) โ) (hX : UnitCols X)
(ฯ : โ) (hฯ : 0 < ฯ) (hs : 1 โค s) (hsp : s โค p) :
(โ u : Fin p โ โ, l0 u โค s โ
(4 + Real.sqrt 2) * ฯ * max (sortedSum u)
(Real.sqrt (Real.log (1 / ((s : โ) / (2 * Real.exp 1 * p)))) * l2 (X.mulVec u)) โค
(4 + Real.sqrt 2) * ฯ * Real.sqrt ((s : โ) * Real.log (2 * Real.exp 1 * p / s)) *
l2 u) โง
F X ฯ ((s : โ) / (2 * Real.exp 1 * p)) โ E X ฯ s := by sorry
end SubsetShrink.Events
Source
Mazumder, Radchenko & Dedieu, Subset Selection with Shrinkage, arXiv:1708.03288v4, p. 38, proof of Theorem 1 (B.1), display after (28) and the sentence after it
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.