Sharp thresholds for high-dimensional and noisy recovery of sparsity

Details Sharp thresholds for high-dimensional and noisy recovery of sparsity Sharp thresholds for high-dimensional and noisy recovery of sparsity

2006-05-30

arxiv.org/abs/math/0605740v1

Mathematics

Statistics Theory

Appeared as Technical Report 708, Department of Statistics, UC Berkeley

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Sharp thresholds for high-dimensional and noisy recovery of sparsity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sharp thresholds for high-dimensional and noisy recovery of sparsity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sharp thresholds for high-dimensional and noisy recovery of sparsity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-467356