Statistical Mechanical Analysis of a Typical Reconstruction Limit of Compressed Sensing

Details Statistical Mechanical Analysis of a Typical Reconstruction Limit of Compressed Sensing Statistical Mechanical Analysis of a Typical Reconstruction Limit of Compressed Sensing

2010-01-25

arxiv.org/abs/1001.4298v2

Computer Science

Information Theory

5 pages, 2 figures, accepted for presentation in ISIT2010

Scientific paper

We use the replica method of statistical mechanics to examine a typical performance of correctly reconstructing $N$-dimensional sparse vector $bx=(x_i)$ from its linear transformation $by=bF bx$ of $P$ dimensions on the basis of minimization of the $L_p$-norm $||bx||_p= lim_{epsilon to +0} sum_{i=1}^N |x_i|^{p+epsilon}$. We characterize the reconstruction performance by the critical relation of the successful reconstruction between the ratio $alpha=P/N$ and the density $rho$ of non-zero elements in $bx$ in the limit $P,,N to infty$ while keeping $alpha sim O(1)$ and allowing asymptotically negligible reconstruction errors. We show that the critical relation $alpha_c(rho)$ holds universally as long as $bF^{rm T}bF$ can be characterized asymptotically by a rotationally invariant random matrix ensemble and $bF bF^{rm T}$ is typically of full rank. This supports the universality of the critical relation observed by Donoho and Tanner ({em Phil. Trans. R. Soc. A}, vol.~367, pp.~4273--4293, 2009; arXiv: 0807.3590) for various ensembles of compression matrices.

Affiliated with

Also associated with

No associations

Rating

Statistical Mechanical Analysis of a Typical Reconstruction Limit of Compressed Sensing 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 Statistical Mechanical Analysis of a Typical Reconstruction Limit of Compressed Sensing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Statistical Mechanical Analysis of a Typical Reconstruction Limit of Compressed Sensing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-130130