Statistical mechanics approach to 1-bit compressed sensing

Yingying Xu, Yoshiyuki Kabashima

TL;DR

This paper applies statistical mechanics to analyze the performance of 1-bit compressed sensing (1-bit CS), a technique that recovers sparse signals from quantized measurements (only their signs). The authors use the replica method to predict performance and develop a new cavity-inspired algorithm that offers better accuracy and speed for denser signals compared to existing methods.

What Problem Does This Paper Address?

Compressed sensing (CS) is a powerful technique for reconstructing high-dimensional sparse signals from fewer measurements than traditionally required. However, real-world applications often involve quantized measurements to reduce data size and hardware complexity. 1-bit CS is a particularly aggressive form of quantization, where only the sign of each linear measurement is retained. This leads to a significant loss of information, making perfect signal recovery impossible and the resulting optimization problem non-convex, which complicates analysis and algorithm design. This paper aims to understand the theoretical performance limits of 1-bit CS, particularly for l1-norm-based recovery schemes, and to develop more efficient algorithms.

Methods

The core of the paper's theoretical analysis relies on statistical mechanics, specifically the replica method. This approach is used to calculate the average performance of signal recovery by analyzing the partition function of the system. The authors employ the replica symmetric (RS) ansatz for their initial analysis, which simplifies the calculations but is later found to be unstable, suggesting the presence of replica symmetry breaking.

To address the limitations of the RS ansatz and to develop a practical algorithm, the paper introduces a cavity-inspired signal recovery algorithm. This algorithm is derived from the principles of statistical mechanics and belief propagation, aiming to overcome the convergence issues encountered with naive iterations of self-consistent equations. The cavity method involves constructing virtual systems by removing parts of the original system to derive self-consistent equations for the parameters.

Datasets

Not discussed in the paper. The evaluation is based on simulated data generated according to the problem setup (sparse signals and random measurement matrices).

Key Insights and Ideas

  • 1-bit CS is inherently challenging: The loss of amplitude information makes perfect recovery impossible, and the non-convexity of the optimization problem leads to multiple local optima.
  • Replica Symmetry Breaking (RSB) is crucial: The initial RS analysis, while providing good MSE predictions, is found to be locally unstable. This indicates that a more complex, replica symmetry-broken solution is needed for a complete theoretical understanding, especially for metrics like false positive/negative rates.
  • Local optima are abundant and similar: The l1-based recovery problem for 1-bit CS has many local optima that yield similar Mean Squared Error (MSE) performance. This explains why approximate algorithms like RFPI can achieve near-optimal MSE.
  • Cavity method offers a path to better algorithms: A new cavity-inspired algorithm is developed that, by incorporating an Onsager reaction term and controlling a macroscopic variable, achieves good convergence and performance.
  • Density matters: The performance of the new cavity-inspired algorithm is particularly advantageous when the density of non-zero entries in the original signal is relatively high.

Key Results

  • The replica method under the RS ansatz provides a good theoretical prediction for the Mean Squared Error (MSE) of the l1-based recovery scheme, showing good agreement with experimental results from an existing algorithm (RFPI).
  • The RS solution is found to be unstable, suggesting the need for RSB analysis for a more accurate understanding of performance, especially for metrics like false positive (FP) and false negative (FN) probabilities.
  • A new cavity-inspired signal recovery algorithm (CISR) is developed.
  • CISR demonstrates better MSE performance than RFPI when the signal's non-zero density is high.
  • CISR is significantly faster than RFPI, offering a substantial computational cost reduction (hundreds of times faster).
  • CISR shows lower FP probabilities and higher FN probabilities compared to RFPI, suggesting it can yield sparser signals.

Limitations and Future Work

  • RSB is not fully addressed: While the paper acknowledges the instability of the RS solution and its implications for FP/FN probabilities, a full RSB analysis is not presented. This is a limitation for precisely predicting these error rates.
  • Algorithm tuning: While the new CISR algorithm reduces the number of tuning parameters from two to one compared to RFPI, it still requires tuning of a parameter (B).
  • Future work suggestions: The authors suggest exploring recovery algorithms based on Bayesian inference and matrix design, similar to approaches used in standard CS, as a promising avenue for 1-bit CS, especially given the inherent difficulties with l1-based convex optimization. They also note that the l1-based scheme's significance might be limited due to its non-convexity.

Summary updated

Abstract

Compressed sensing is a framework that makes it possible to recover an N-dimensional sparse vector x∈RN from its linear transformation y∈RM 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 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 abovementioned scheme and does so with a lower computational cost.
BibTeX
@inproceedings{xu2016statistical,
  author = {Yingying Xu and Yoshiyuki Kabashima},
  title = {{Statistical mechanics approach to 1-bit compressed sensing}},
  booktitle = {Tokyo},
  year = {2016},
}
Figure