A typical reconstruction limit for compressed sensing based on Lp-norm minimization
We consider the problem of reconstructing an Ndimensional continuous vector x from P constraints which are generated from its linear transformation under the assumption that the number of non-zero elements of a; is typically limited to pN (0 ≤ p ≤ 1). Problems of this type can be solved by minimizing a cost function with respect to the Lp-norm ||x||p=limε→+0∑(i=1)N|xi|p+ε subject to the constraints under an appropriate condition. For several values of p. we assess a typical case limit ac(p), which represents a critical relation between a=P/N and p for successfully reconstructing the original vector by the minimization for typical situations in the limit N, P→ oo while keeping a finite, utilizing the replica method. For p=1, ac(p) is considerably smaller than its worst case counterpart, which has been rigorously derived in the existing literature on information theory.
analysis of algorithms robust, and stochastic optimization source and channel coding communication supply and information networks
Kabashima T Wadayama T Tanaka
Department of Computer Science, Nagoya Institute of Technology, Nagoya 466-8555, Japan Department of Computational Intelligence and Systems Science, Tokyo Institute of Technology, Yokoham Department of Systems Science, Kyoto University, Kyoto 606-8501, Japan
国际会议
International Workshop on Statistical Physics and Computer Sciences(统计物理与计算机科学交叉研究国际研讨会 )
北京
英文
62-73
2010-07-08（万方平台首次上网日期，不代表论文的发表时间）