Sharp thresholds for high-dimensional and noisy recovery of sparsity
<|reference_start|>Sharp thresholds for high-dimensional and noisy recovery of sparsity: The problem of consistently estimating the sparsity pattern of a vector $\betastar \in \real^\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 $\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 $\mdim$, the number $\spindex$ of non-zero elements in $\betastar$, and the number of observations $\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 $\ThreshLow$ and $\ThreshUp$ with the following properties: for any $\epsilon > 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 $\ThreshLow = \ThreshUp = 1$, so that the threshold is sharp and exactly determined.<|reference_end|>
@article{wainwright2006sharp,
    title={Sharp thresholds for high-dimensional and noisy recovery of sparsity},
    author={Martin J. Wainwright},
    journal={arXiv preprint arXiv:math/0605740},
    year={2006},
    archivePrefix={arXiv},
    eprint={math/0605740},
    primaryClass={math.ST cs.IT math.IT stat.TH}
}