2010/10/11 by Xu, Weiyu, Tang, Ao
#FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.1010.2236
ℓ1 minimization can be used to recover sufficiently sparse unknown signals from compressed linear measurements. In fact, exact thresholds on the sparsity (the size of the support set), under which with high probability a sparse signal can be recovered from i.i.d. Gaussian measurements, have been computed and are referred to as "weak thresholds" \citeD. It was also known that there is a tradeoff between the sparsity and the ℓ1 minimization recovery stability. In this paper, we give a closed-form characterization for this tradeoff which we call the scaling law for compressive sensing recovery stability. In a nutshell, we are able to show that as the sparsity backs off \varpi (0