Statistical mechanics approach to 1-bit compressed sensing

DOI10.1088/1742-5468/2013/02/P02041zbMATH Open1456.94021arXiv1301.1423OpenAlexW3099838995MaRDI QIDQ3301530FDOQ3301530

Authors: Yoshiyuki Kabashima, Yingying Xu 

Publication date: 11 August 2020

Published in: Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Abstract: Compressed sensing is a technique for recovering a high-dimensional signal from lower-dimensional data, whose components represent partial information about the signal, utilizing prior knowledge on the sparsity of the signal. For further reducing the data size of the compressed expression, a scheme to recover the original signal utilizing only the sign of each entry of the linearly transformed vector was recently proposed. This approach is often termed the 1-bit compressed sensing. Here we analyze the typical performance of an L1-norm based signal recovery scheme for the 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 a 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 abovementioned scheme and does so with a lower computational cost.

Full work available at URL: https://arxiv.org/abs/1301.1423

Recommendations

• Bayesian signal reconstruction for 1-bit compressed sensing
• Statistical mechanics analysis of thresholding 1-bit compressed sensing
• One-bit compressed sensing by linear programming
• 1-bit compressive sensing: reformulation and RRSP-based sign recovery theory
• One-bit compressive sensing of dictionary-sparse signals

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Classical equilibrium statistical mechanics (general) (82B05)

Cites Work

• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Sparse and redundant representations. From theory to applications in signal and image processing.
• Compressed sensing
• Title not available (Why is that?)
• Sparse image and signal processing. Wavelets, curvelets, morphological diversity
• Good error-correcting codes based on very sparse matrices
• A CDMA multiuser detection algorithm on the basis of belief propagation
• Information, Physics, and Computation
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
• Introduction to the replica theory of disordered statistical systems
• Self-consistent signal-to-noise analysis and its application to analogue neural networks with asymmetric connections

Cited In (12)

• Stability of 1-bit compressed sensing in sparse data reconstruction
• One-bit sensing, discrepancy and Stolarsky's principle
• Phase transitions in \(q\)-states signal reconstruction
• Bayesian signal reconstruction for 1-bit compressed sensing
• Statistical mechanics analysis of thresholding 1-bit compressed sensing
• Active online learning in the binary perceptron problem
• 1-bit compressive sensing: reformulation and RRSP-based sign recovery theory
• Robust 1-bit compressed sensing via hinge loss minimization
• An approach to one-bit compressed sensing based on probably approximately correct learning theory
• One-bit compressed sensing by linear programming
• Approximate message passing for nonconvex sparse regularization with stability and asymptotic analysis
• Critical behavior and universality classes for an algorithmic phase transition in sparse reconstruction

This page was built for publication: Statistical mechanics approach to 1-bit compressed sensing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3301530)