Multi-Stage Dantzig Selector

Abstract

We consider the following sparse signal recovery (or feature selection) problem: given a design matrix X R^n m (m n) and a noisy observation vector y R^n 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 l_p norm (p 1) is bounded as equation* \| - ^*\|_p (C(s-N)^1/p m+ ) , equation* 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( m). The proposed method improves the estimation bound of the standard Dantzig selector approximately from Cs^1/p m to C(s-N)^1/p m 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.

Tasks

Reproductions