查看文章

In many important statistical applications, the number of variables or parameters p is much larger than the number of observations n. Suppose then that we have observations y=Xβ+z, where β∈R^p is a parameter vector of interest, X is a data matrix with possibly far fewer rows than columns, n≪p, and the z_i’s are i.i.d. N(0, σ²). Is it possible to estimate β reliably based on the noisy data y?

To estimate β, we introduce a new estimator—we call it the Dantzig selector—which is a solution to the ℓ₁-regularization problem $$\min_{\tilde{\beta}\in\mathbf{R}^{p}}\|\tilde{\beta}\|_{\ell_{1}}\quad\mbox{subject to}\quad \|X^{*}r\|_{\ell_{\infty}}\leq(1+t^{-1})\sqrt{2\log p}\cdot\sigma,$$ where r is the residual vector y−Xβ̃ and t is a positive scalar. We show that if X obeys a uniform uncertainty principle (with unit-normed columns) and if the true parameter vector β is sufficiently sparse (which here roughly guarantees that the …