# A Multi-Stage Framework for Dantzig Selector and LASSO

Ji Liu, Peter Wonka, Jieping Ye.

Year: 2012, Volume: 13, Issue: 41, Pages: 1189−1219

#### Abstract

We consider the following sparse signal recovery (or feature selection) problem: given a design matrix *X∈ ℝ ^{n✕ m}*

*(m >> n)*and a noisy observation vector

*y∈ ℝ*satisfying

^{n}*y=Xβ*where

^{*}+ε*ε*is the noise vector following a Gaussian distribution

*N(0,σ*, how to recover the signal (or parameter vector)

^{2}I)*β*when the signal is sparse?

^{*}The Dantzig selector has been proposed for sparse signal recovery with strong theoretical guarantees. In this paper, we propose a multi-stage Dantzig selector method, which iteratively refines the target signal

*β*. We show that if

^{*}*X*obeys a certain condition, then with a large probability the difference between the solution

*β̂*estimated by the proposed method and the true solution

*β*measured in terms of the

^{*}*l*norm (

_{p}*p≥ 1*) is bounded as

||β̂-β

^{*}||

_{p}≤ (C(s-N)

^{1/p}√log m+Δ)σ,

where

*C*is a constant,

*s*is the number of nonzero entries in

*β*, the risk of the oracle estimator

^{*}*Δ*is independent of

*m*and is much smaller than the first term, and

*N*is the number of entries of

*β*larger than a certain value in the order of

^{*}*O(σ√log m)*. The proposed method improves the estimation bound of the standard Dantzig selector approximately from

*Cs*to

^{1/p}√log mσ*C(s-N)*where the value

^{1/p}√log mσ*N*depends on the number of large entries in

*β*. When

^{*}*N=s*, the proposed algorithm achieves the oracle solution with a high probability, where the oracle solution is the projection of the observation vector

*y*onto true features. In addition, with a large probability, the proposed method can select the same number of correct features under a milder condition than the Dantzig selector. Finally, we extend this multi-stage procedure to the LASSO case.