The problem of estimating a sparse signal embedded in noise arises in various contexts, including signal denoising and approximation, as well as graphical model selection. The natural optimization-theoretic formulation of such problems involves "norm" constraints (i.e., penalties on the number of non-zero coefficients), which leads to NP-hard problems in general. A natural approach is to consider the use of the -norm as a computationally tractable surrogate, as has been pursued in both signal processing and statistics.