Processing math: 100%
Skip to yearly menu bar Skip to main content


Poster

Multi-Stage Dantzig Selector

Ji Liu · Peter Wonka · Jieping Ye


Abstract: We consider the following sparse signal recovery (or feature selection) problem: given a design matrix XRn×m (mn) and a noisy observation vector yRn satisfying y=Xβ+ϵ where ϵ is the noise vector following a Gaussian distribution N(0,σ2I), how to recover the signal (or parameter vector) β 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 lp norm (p1) is bounded as ˆββp(C(sN)1/plogm+Δ)σ, C is a constant, s is the number of nonzero entries in β, Δ 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(σlogm). The proposed method improves the estimation bound of the standard Dantzig selector approximately from Cs1/plogmσ to C(sN)1/plogmσ where the value N depends on the number of large entries in β. When N=s, the proposed algorithm achieves the oracle solution with a high probability. 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.

Live content is unavailable. Log in and register to view live content