2006/05/30 by Martin J. Wainwright, Wainwright, Martin J. · 8 citations
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Image and Signal Denoising Methods #Information Theory (cs.IT) #Mathematical Analysis and Transform Methods #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.math/0605740
openalex publication_date 2006/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The problem of consistently estimating the sparsity pattern of a vector \betastar ∈ \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 ℓ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 ε> 0, if \numobs > 2 (\ThreshUp + ε) 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 - ε) 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.