Paper Info
Title
Statistical mechanics approach to 1-bit compressed sensing
Abstract
Compressed sensing is a framework that makes it possible to recover an N-dimensional sparse vector x is an element of R-N from its linear transformation y is an element of R-M 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. Here, we analyze the typical performance of an l(1)-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 l(1)-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 abovementioned scheme and does so with a lower computational cost.
Year
DOI
Venue
2013
10.1088/1742-5468/2013/02/P02041
JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT
Keywords
Field
DocType
analysis of algorithms,source and channel coding,error correcting codes
Ansatz,Replica,Mathematical optimization,Statistical mechanics,Quantum mechanics,Local optimum,Analysis of algorithms,Cavity method,Algorithm,Curse of dimensionality,Mathematics,Compressed sensing
Journal
Volume
Issue
ISSN
abs/1301.1423
02
1742-5468
Citations 
PageRank 
References 
0
0.34
0
Authors
2
Name
Order
Citations
PageRank
Yingying Xu111.98
Yoshiyuki Kabashima213627.83