Statistical Mechanical Analysis of a Typical Reconstruction Limit of Compressed Sensing

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 TbF$ 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: <a href="/abs/0807.3590">0807.3590</a>) for various ensembles of compression matrices.