|
Abstract摘要
|
Compressed sensing is a framework that makes it possible to recover an N-dimensional sparse vector x from its linear transformation y of lower dimensionality M < N. A scheme further reducing the data size of the compressed expression by using only the sign of each entry of y to recover x was recently proposed. This is often termed 1-bit compressed sensing. In this talk, we analyze the typical performance of an l1-norm-based signal recovery scheme for 1-bit compressed sensing using statistical mechanics methods. We show that the signal recovery performance predicted by the replica method under the replica symmetric ansatz, which turns out to be locally unstable for modes breaking the replica symmetry, is in good consistency with experimental results of an approximate recovery algorithm developed earlier. This suggests that the l1-based recovery problem typically has many local optima of a similar recovery accuracy, which can be achieved by the approximate algorithm. We also develop another approximate recovery algorithm inspired by the cavity method. Numerical experiments show that when the density of nonzero entries in the original signal is relatively large the new algorithm offers better performance than the above-mentioned scheme and does so with a lower computational cost. |
