(27), p. 38 — ‖Xu‖ ≤ ‖u‖₁ ≤ √s‖u‖ and √log(1/δ₀)‖Xu‖ ≤ √(s log(2ep/s))‖u‖ at δ₀ = s/(2ep)
ProvedSubsetShrink.Events.eq_27Let have columns of unit Euclidean norm, let , and let satisfy . Then , and with ,
This is the first step of the proof of Theorem 1 that reduces the event to the event : at this value of , the second entry of the maximum in is dominated by the threshold of .
Formalization Note is substituted directly, so appears as Real.log (1 / (s / (2 * exp 1 * p))). Norms are the explicit Euclidean and norms on Fin p → ℝ.
Preamble
import Mathlib import Definitions.Def_SubsetShrink_Events_Model open MeasureTheory ProbabilityTheory
Formal statement
namespace SubsetShrink.Events
theorem eq_27 {n p s : ℕ} (X : Matrix (Fin n) (Fin p) ℝ) (hX : UnitCols X)
(hs : 1 ≤ s) (hsp : s ≤ p) (u : Fin p → ℝ) (hu : l0 u ≤ s) :
l2 (X.mulVec u) ≤ l1 u ∧ l1 u ≤ Real.sqrt s * l2 u ∧
Real.sqrt (Real.log (1 / ((s : ℝ) / (2 * Real.exp 1 * p)))) * l2 (X.mulVec u) ≤
Real.sqrt ((s : ℝ) * Real.log (2 * Real.exp 1 * p / s)) * l2 u := by sorry
end SubsetShrink.Events
Source
Mazumder, Radchenko & Dedieu, Subset Selection with Shrinkage, arXiv:1708.03288v4, p. 38, proof of Theorem 1 (B.1), (27) and the sentence before it
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.