科研之友
微信
新浪微博
Facebook
分享链接
摘要
We consider the following sparse signal recovery (or feature selection) problem: given a design matrix X is an element of R-nxm (m >> n) and a noisy observation vector y is an element of R-n satisfying y = X beta* + epsilon where e is the noise vector following a Gaussian distribution N(0, sigma I-2), how to recover the signal (or parameter vector) beta* 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 beta*. We show that if X obeys a certain condition, then with a large probability the difference between the solution (beta) over cap estimated by the proposed method and the true solution beta* measured in terms of the l(p) norm (p >= 1) is bounded as
parallel to(beta) over cap-beta*parallel to p <= (C(s-N)(1/p) root logm+Delta)sigma,
where C is a constant, s is the number of nonzero entries in beta*, the risk of the oracle estimator Delta is independent of m and is much smaller than the first term, and N is the number of entries of beta* larger than a certain value in the order of O(sigma root logm). The proposed method improves the estimation bound of the standard Dantzig selector approximately from Cs-1/p root logm sigma to C(s-N)(1/p) root logm sigma where the value N depends on the number of large entries in beta*. 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.
- 出版日期2012-4
