Sharp thresholds for high-dimensional and noisy recovery of sparsity

The problem of consistently estimating the sparsity pattern of a vector ∈ ^ 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 ₁-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 , the number of non-zero elements in , and the number of observations 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 and with the following properties: for any $ε> 0$, if > 2 ( + ε) log ( - ) + + 1, then the Lasso succeeds in recovering the sparsity pattern with probability converging to one for large problems, whereas for < 2 ( - ε) log ( - ) + + 1, then the probability of successful recovery converges to zero. For the special case of the uniform Gaussian ensemble, we show that = = 1, so that the threshold is sharp and exactly determined.