The Dantzig selector and sparsity oracle inequalities

Let Yⱼ=f_(Xⱼ)+ξⱼ, j=1,, n, where X, X₁,, Xₙ are i.i.d. random variables in a measurable space (S,A) with distribution Π and ξ, ξ₁, ,ξₙ are i.i.d. random variables with Eξ=0 independent of (X₁,, Xₙ). Given a dictionary h₁,, hN: S↦ R, let fλ:=∑ⱼ₌₁N λⱼ hⱼ, λ=(λ₁,, λN)∈ RN. Given ε>0, define Λε:=\λ∈ RN: max1≤ k≤ N |n⁻¹∑ⱼ₌₁ⁿ (fλ(Xⱼ)-Yⱼ)hₖ(Xⱼ)| ≤ε \ and λ:=λε∈ Argmin_λ∈Λε\|λ\| ₁. In the case where f_:=f_λ^, λ^∈ RN, Candes and Tao Ann. Statist. 35 (2007) 2313-2351] suggested using λ as an estimator of λ^. They called this estimator “the Dantzig selector”. We study the properties of fλ as an estimator of f_ for regression models with random design, extending some of the results of Candes and Tao (and providing alternative proofs of these results).