Abstract

We consider the following sparse signal recovery (or feature selection) problem: given a design matrix X and a noisy observation vector satisfying where is the noise vector following a Gaussian distribution 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 norm is bounded as where C is a constant, s is the number of nonzero entries in is independent of 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 The proposed method improves the ? estimation bound of the  standard Dantzig selector approximately from 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.