Statistical mechanics approach to 1-bit compressed sensing

Yingying Xu, Yoshiyuki Kabashima

Abstract

Compressed sensing (CS) is a transformative technique for recovering high-dimensional signals from sparse, lower-dimensional data. While traditional CS relies on precise linear measurements, real-world hardware often requires quantization. The extreme limit of this is 1-bit compressed sensing, where only the sign of each measurement is recorded. This paper analyzes the performance of $l_1$-norm based recovery for 1-bit CS using statistical mechanics. By employing the replica and cavity methods, the authors reveal a complex, "glassy" optimization landscape where local optima nonetheless provide consistent recovery accuracy. Furthermore, they introduce the Cavity-inspired Signal Recovery (CISR) algorithm, which offers a significant computational speedup over existing state-of-the-art methods.

Introduction: The Challenge of 1-bit Quantization

In standard compressed sensing, we aim to recover a sparse signal $x \in \mathbb{R}^N$ from a small number of linear measurements $y = \Phi x$, where $M < N$. However, practical implementation in digital systems necessitates quantization. 1-bit compressed sensing represents the most aggressive form of this, where measurements are reduced to a single bit: $y = \text{sign}(\Phi x)$.

This scheme is highly attractive for hardware design because it only requires a simple comparator rather than a high-resolution analog-to-digital converter, drastically reducing data storage and transmission costs. However, the non-linearity of the sign function destroys the convexity of the recovery problem. Traditional $l_1$-minimization, which works seamlessly for continuous measurements, becomes a non-convex challenge in the 1-bit regime.

Geometric comparison of standard CS (a) and 1-bit CS (b). In 1-bit CS, the measurement defines a half-space (yellow region) rather than a hyperplane.

Theoretical Framework: Replica and Cavity Methods

To understand the fundamental limits of 1-bit recovery, the authors turned to tools from the physics of disordered systems. They specifically analyzed the typical performance of an $l_1$-norm minimization scheme under the constraint of the observed signs.

The Replica Method

The researchers used the Replica Method to predict the Mean Square Error (MSE) of the recovery. Under the Replica Symmetric (RS) ansatz, they found that the system enters a "glassy" phase. This state is locally unstable, implying that the optimization landscape is riddled with many local minima. In physical terms, this suggests that the problem of finding the global $l_1$ minimum is computationally hard because the algorithm can easily get trapped in these sub-optimal states.

The Cavity Method and CISR

While the replica method provides a static view of the system's equilibrium, the Cavity Method allows for the derivation of dynamic message-passing algorithms. This led to the development of the Cavity-inspired Signal Recovery (CISR) algorithm.

A critical component of CISR is the inclusion of the Onsager reaction term. In iterative algorithms, estimates can become biased by their own previous values (self-feedback). The Onsager term mathematically cancels this feedback, ensuring that the messages passed between "nodes" in the algorithm remain statistically independent. This leads to much faster and more stable convergence compared to previous double-loop algorithms like Renormalized Fixed Point Iteration (RFPI).

Key Insights: The "Good Enough" Local Optima

One of the paper's most surprising findings is that despite the non-convexity and the presence of many local optima, the recovery performance is remarkably robust. The authors demonstrated that these local optima are clustered in terms of their accuracy. Even if an algorithm like CISR gets trapped in a local minimum, the resulting MSE is very close to the theoretical global minimum predicted by the replica method. This explains why approximate algorithms can perform so well in practice despite the theoretical complexity of the underlying optimization.

However, the analysis also revealed an "$l_1$ floor." Even with an infinite number of measurements, $l_1$-based recovery for 1-bit CS will always have a finite probability of "False Positives" (misidentifying zero entries as non-zero). This suggests that while $l_1$ is a powerful heuristic, it is not the absolute optimal cost function for 1-bit scenarios.

Experimental Results and Performance

The authors validated their theoretical predictions using synthetic datasets where signals were drawn from a Bernoulli-Gaussian distribution. The results were striking:

  • Theoretical Validation: The MSE predicted by the replica method perfectly matched the experimental results of existing algorithms, confirming the utility of the statistical mechanics approach.
  • Computational Speed: The CISR algorithm proved to be hundreds of times faster than RFPI. In one test case ($N=128, K=32$), RFPI required approximately 35 seconds to converge, while CISR achieved the same or better accuracy in just 0.02 seconds.
  • Ease of Use: CISR simplifies the recovery process by reducing the number of sensitive tuning parameters from two down to one, making it more practical for real-world applications.

Conclusion and Future Directions

This research provides a rigorous foundation for 1-bit compressed sensing, bridging the gap between information theory and statistical physics. By showing that the "glassy" nature of the problem does not necessarily prevent accurate signal recovery, the authors have opened the door for more efficient hardware-software co-design in sensing systems.

Future work may explore Bayesian inference methods to bypass the inherent limitations of $l_1$-minimization, potentially eliminating the "False Positive" floor and further pushing the boundaries of what can be recovered from a single bit of information.

Summary updated

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.
BibTeX
@inproceedings{xu2016statistical,
  author = {Yingying Xu and Yoshiyuki Kabashima},
  title = {{Statistical mechanics approach to 1-bit compressed sensing}},
  booktitle = {Tokyo},
  year = {2016},
}
Figure