Computer Science – Information Theory
Scientific paper
2010-10-11
Computer Science
Information Theory
Report
Scientific paper
$\ell_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" \cite{D}. It was also known that there is a tradeoff between the sparsity and the $\ell_1$ minimization recovery stability. In this paper, we give a \emph{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<\varpi<1$) from the weak threshold of $\ell_1$ recovery, the parameter for the recovery stability will scale as $\frac{1}{\sqrt{1-\varpi}}$. Our result is based on a careful analysis through the Grassmann angle framework for the Gaussian measurement matrix. We will further discuss how this scaling law helps in analyzing the iterative reweighted $\ell_1$ minimization algorithms. If the nonzero elements over the signal support follow an amplitude probability density function (pdf) $f(\cdot)$ whose $t$-th derivative $f^{t}(0) \neq 0$ for some integer $t \geq 0$, then a certain iterative reweighted $\ell_1$ minimization algorithm can be analytically shown to lift the phase transition thresholds (weak thresholds) of the plain $\ell_1$ minimization algorithm.
Tang Ao
Xu Weiyu
No associations
LandOfFree
On the Scaling Law for Compressive Sensing and its Applications 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 On the Scaling Law for Compressive Sensing and its Applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Scaling Law for Compressive Sensing and its Applications will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-607135