Computer Science – Information Theory
Scientific paper
2009-07-06
J. Stat. Mech. (2009) L09003 (12 pages)
Computer Science
Information Theory
12 pages, 2 figures
Scientific paper
We consider the problem of reconstructing an $N$-dimensional continuous vector $\bx$ from $P$ constraints which are generated by its linear transformation under the assumption that the number of non-zero elements of $\bx$ is typically limited to $\rho N$ ($0\le \rho \le 1$). Problems of this type can be solved by minimizing a cost function with respect to the $L_p$-norm $||\bx||_p=\lim_{\epsilon \to +0}\sum_{i=1}^N |x_i|^{p+\epsilon}$, subject to the constraints under an appropriate condition. For several $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 minimization for typical situations in the limit $N,P \to \infty$ with 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 by existing literature of information theory.
Kabashima Yoshiyuki
Tanaka Toshiaki
Wadayama Tadashi
No associations
LandOfFree
A typical reconstruction limit of compressed sensing based on Lp-norm minimization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A typical reconstruction limit of compressed sensing based on Lp-norm minimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A typical reconstruction limit of compressed sensing based on Lp-norm minimization will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-27153