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 ρN (0≤ρ≤1). Problems of this type can be solved by minimizing a cost function with respect to the Lp-norm ||x||p= lim ε→+0Σi=1N |xi|p+ε, subject to the constraints under an appropriate condition. For several values of p, we assess a typical case limit αc(ρ), which represents a critical relation between α = P/N and ρ for successfully reconstructing the original vector by the minimization for typical situations in the limit N,P→∞ while keeping α finite, utilizing the replica method. For p = 1, αc(ρ) is considerably smaller than its worst case counterpart, which has been rigorously derived in the existing literature on information theory. (letter)