A typical reconstruction limit of compressed sensing based on Lp-norm minimization
We consider the problem of reconstructing an -dimensional continuous vector $\bx$ from constraints which are generated by its linear transformation under the assumption that the number of non-zero elements of $\bx$ is typically limited to (). Problems of this type can be solved by minimizing a cost function with respect to the -norm $||\bx||_p=\lim_{ε\to +0}\sum_{i=1}^N |x_i|^{p+ε}$, subject to the constraints under an appropriate condition. For several , we assess a typical case limit , which represents a critical relation between and for successfully reconstructing the original vector by minimization for typical situations in the limit with keeping finite, utilizing the replica method. For , is considerably smaller than its worst case counterpart, which has been rigorously derived by existing literature of information theory.