Given n noisy samples with p dimensions, where n ≪ p, we show that the multi-step thresholding procedure based on the Lasso -we call it the Thresholded Lasso, can accurately estimate a sparse vector β ∈ R p in a linear model Y = Xβ + ǫ, where X n×p is a design matrix normalized to have column ℓ 2 norm √ n, and ǫ ∼ N (0, σ 2 I n ). We show that under the restricted eigenvalue (RE) condition (Bickel-Ritov-Tsybakov 09), it is possible to achieve the ℓ 2 loss within a logarithmic factor of the ideal mean square error one would achieve with an oracle while selecting a sufficiently sparse model -hence achieving sparse oracle inequalities; the oracle would supply perfect information about which coordinates are non-zero and which are above the noise level. In some sense, the Thresholded Lasso recovers the choices that would have been made by the ℓ 0 penalized least squares estimators, in that it selects a sufficiently sparse model without sacrificing the accuracy in estimating β and in predicting Xβ. We also show for the Gauss-Dantzig selector (Candès-Tao 07), if X obeys a uniform uncertainty principle and if the true parameter is sufficiently sparse, one will achieve the sparse oracle inequalities as above, while allowing at most s 0 irrelevant variables in the model in the worst case, where s 0 ≤ s is the smallest integer such that for λ = 2 log p/n, Our simulation results on the Thresholded Lasso match our theoretical analysis excellently.
In REF , it is shown that a multi-step thresholding procedure can accurately estimate a sparse vector β ∈ R p under the restricted eigenvalue condition of Bickel et al. [2009] .
Thresholded Lasso for high dimensional variable selection and statistical estimation
arXiv: Statistics Theory
Mathematics