  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.
