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 x = (x_i) from its linear transformation y = Fx of P dimensions on the basis of minimization of the L_p-norm ∥x∥_p = lim_∈→+0 Σ^N_i=1 |x_i|^p+∈. We characterize the reconstruction performance by the critical relation of the successful reconstruction between the ratio α = P/N and the density ρ of non-zero elements in x in the limit P, N → ∞ while keeping α ~ O(1) and allowing asymptotically negligible reconstruction errors. We show that the critical relation α_c(ρ) holds universally as long as F^T F can be characterized asymptotically by a rotationally invariant random matrix ensemble and FF^T is typically of full rank. This supports the universality of the critical relation observed by Donoho and Tanner (Phil. Trans. R. Soc. A, vol. 367, pp. 4273-4293, 2009; arXiv: 0807.3590) for various ensembles of compression matrices.