Sharp thresholds for high-dimensional and noisy recovery of sparsity

The problem of consistently estimating the sparsity pattern of a vector $\text{betastar}\in {\mathrm{\Re }}^{\text{mdim}}$ based on observations contaminated by noise arises in various contexts, including subset selection in regression, structure estimation in graphical models, sparse approximation, and signal denoising. We analyze the behavior of ${\mathrm{\ell }}_1$-constrained quadratic programming (QP), also referred to as the Lasso, for recovering the sparsity pattern. Our main result is to establish a sharp relation between the problem dimension $\text{mdim}$, the number $\text{spindex}$ of non-zero elements in $\text{betastar}$, and the number of observations $\text{numobs}$ that are required for reliable recovery. For a broad class of Gaussian ensembles satisfying mutual incoherence conditions, we establish existence and compute explicit values of thresholds $\text{ThreshLow}$ and $\text{ThreshUp}$ with the following properties: for any $ϵ>0$, if $\numobs

2 (\ThreshUp + \epsilon) \log (\mdim - \spindex) + \spindex + 1$, then the Lasso succeeds in recovering the sparsity pattern with probability converging to one for large problems, whereas for $\numobs < 2 (\ThreshLow - \epsilon) \log (\mdim - \spindex) + \spindex + 1$, then the probability of successful recovery converges to zero. For the special case of the uniform Gaussian ensemble, we show that $\text{ThreshLow}=\text{ThreshUp}=1$, so that the threshold is sharp and exactly determined.