Thresholded Lasso for high dimensional variable selection and statistical estimation

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 β∈ ᵖ in a linear model $Y = X β+ ε$, where Xn × p is a design matrix normalized to have column ₂ norm √n, and ε~ N(0, σ² Iₙ). We show that under the restricted eigenvalue (RE) condition (Bickel-Ritov-Tsybakov 09), it is possible to achieve the ₂ 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 ₀ 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₀ irrelevant variables in the model in the worst case, where s₀ ≤ s is the smallest integer such that for λ= √2 log p/n, ∑ᵢ₌₁ᵖ min(βᵢ², λ² σ²) ≤ s₀ λ² σ². Our simulation results on the Thresholded Lasso match our theoretical analysis excellently.