Statistical Mechanical Analysis of a Typical Reconstruction Limit of Compressed Sensing

Abstract

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=bFbx$ of $P$ dimensions on the basis of minimization of the $L_p$-norm $||bx|{|}_p=li{m}_{epsilonto+0}su{m}_{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,,Ntoinfty$ while keeping $alphasimO(1)$ and allowing asymptotically negligible reconstruction errors. We show that the critical relation $alph{a}_c(rho)$ holds universally as long as $b{F}^{rmT}bF$ can be characterized asymptotically by a rotationally invariant random matrix ensemble and $bFb{F}^{rmT}$ 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.

arXiv comment5 pages, 2 figures, accepted for presentation in ISIT2010

Cited by in corpus (1)

• Optimal Phase Transitions in Compressed Sensing