Compressed Sensing over $\ell_p$-balls: Minimax Mean Square Error

Details Compressed Sensing over $\ell_p$-balls: Minimax Mean Square Error Compressed Sensing over $\ell_p$-balls: Minimax Mean Square Error

2011-03-10

arxiv.org/abs/1103.1943v2

Computer Science

Information Theory

41 pages, 11 pdf figures

Scientific paper

We consider the compressed sensing problem, where the object $x_0 \in \bR^N$ is to be recovered from incomplete measurements $y = Ax_0 + z$; here the sensing matrix $A$ is an $n \times N$ random matrix with iid Gaussian entries and $n < N$. A popular method of sparsity-promoting reconstruction is $\ell^1$-penalized least-squares reconstruction (aka LASSO, Basis Pursuit). It is currently popular to consider the strict sparsity model, where the object $x_0$ is nonzero in only a small fraction of entries. In this paper, we instead consider the much more broadly applicable $\ell_p$-sparsity model, where $x_0$ is sparse in the sense of having $\ell_p$ norm bounded by $\xi \cdot N^{1/p}$ for some fixed $0 < p \leq 1$ and $\xi > 0$. We study an asymptotic regime in which $n$ and $N$ both tend to infinity with limiting ratio $n/N = \delta \in (0,1)$, both in the noisy ($z \neq 0$) and noiseless ($z=0$) cases. Under weak assumptions on $x_0$, we are able to precisely evaluate the worst-case asymptotic minimax mean-squared reconstruction error (AMSE) for $\ell^1$ penalized least-squares: min over penalization parameters, max over $\ell_p$-sparse objects $x_0$. We exhibit the asymptotically least-favorable object (hardest sparse signal to recover) and the maximin penalization. Our explicit formulas unexpectedly involve quantities appearing classically in statistical decision theory. Occurring in the present setting, they reflect a deeper connection between penalized $\ell^1$ minimization and scalar soft thresholding. This connection, which follows from earlier work of the authors and collaborators on the AMP iterative thresholding algorithm, is carefully explained. Our approach also gives precise results under weak-$\ell_p$ ball coefficient constraints, as we show here.

Affiliated with

Also associated with

No associations

Rating

Compressed Sensing over $\ell_p$-balls: Minimax Mean Square Error 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 Compressed Sensing over $\ell_p$-balls: Minimax Mean Square Error, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compressed Sensing over $\ell_p$-balls: Minimax Mean Square Error will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-630470