The Dantzig selector: statistical estimation when $p$ is much larger than $n$

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 \beta + z$, where $\beta \in \R^p$ is a parameter vector of interest, $X$ is a data matrix with possibly far fewer rows than columns, $\nrow \ll \ncol$, and the $z_i$'s are i.i.d. $N(0,\sigma^2)$. Is it possible to estimate $\beta$ reliably based on the noisy data $y$? To estimate $\beta$, we introduce a new estimator--which we call the {\em Dantzig selector}--which is solution to an $\ell_1$-regularization problem. We show that if $X$ obeys a uniform uncertainty principle (with unit-normed columns) and if the true parameter vector $\beta$ is sufficiently sparse (which here roughly guarantees that the model is identifiable), then with very large probability, the mean squared error is bounded by the ideal mean squared error, up to a logarithmic loss. In multivariate regression and from a model selection viewpoint, our result says that it is possible nearly to select the best subset of variables, by solving a very simple convex program, which in fact can easily be recast as a convenient linear program (LP).