A typical reconstruction limit for compressed sensing based on Lp-norm minimization

We consider the problem of reconstructing an N-dimensional continuous vector x from P constraints which are generated from its linear transformation under the assumption that the number of non-zero elements of x is typically limited to rho N (0 <= rho <= 1). Problems of this type can be solved by minimizing a cost function with respect to the L-p-norm parallel to x parallel to(p) = lim(epsilon ->+0) Sigma(N)(i=1) vertical bar x(i)vertical bar(p+epsilon), subject to the constraints under an appropriate condition. For several values of p, we assess a typical case limit alpha(c)(rho), which represents a critical relation between alpha = P/N and rho for successfully reconstructing the original vector by the minimization for typical situations in the limit N, P -> infinity while keeping alpha finite, utilizing the replica method. For p = 1, alpha(c)(rho) is considerably smaller than its worst case counterpart, which has been rigorously derived in the existing literature on information theory.