Binary and Multi-Bit Coding for Stable Random Projections

Ping Li

Abstract

This paper presents a robust framework for estimating the $l_\alpha$ norm of signals using quantized measurements, specifically 1-bit (sign) and multi-bit schemes. By employing a Bartlett correction to a closed-form Maximum Likelihood Estimator (MLE), the research demonstrates that highly compressed data can achieve estimation accuracy comparable to full-precision measurements. This approach eliminates the requirement for prior knowledge of signal sparsity in compressed sensing applications, facilitating more practical hardware implementations.

Introduction

Compressed Sensing (CS) traditionally relies on high-precision linear measurements to recover sparse signals. However, physical hardware constraints often necessitate quantization. The most extreme case, 1-bit CS, preserves only the sign of measurements, offering significant advantages in storage and transmission efficiency. A major hurdle in 1-bit CS is the loss of signal scale; most existing algorithms require the signal's sparsity ($K$) or $l_2$ norm as an input. This paper addresses this gap by providing a method to estimate the $l_\alpha$ norm directly from quantized data.

Methodology: Stable Random Projections and Quantized MLE

The core of the proposed method involves Stable Random Projections, where the sensing matrix is drawn from an $\alpha$-stable distribution ($0 < \alpha \leq 2$). This family encompasses Gaussian ($\alpha=2$) and Cauchy ($\alpha=1$) distributions.

The author derives a Maximum Likelihood Estimator (MLE) for the scale parameter $\Lambda_\alpha$ based on comparing measurements against a threshold $C$. For 1-bit coding, a measurement is recorded as "0" if it falls below $C$ and "1" otherwise. To address the inherent bias of the MLE at small sample sizes ($n$), a Bartlett correction is applied.

Optimal variance and threshold parameter $\eta$ as a function of the stable distribution parameter $\alpha$.

The framework extends to multi-bit coding (e.g., 2-bit with 3 thresholds), which reduces variance and decreases sensitivity to the choice of thresholds. This multi-bit approach involves solving nonlinear equations but offers greater stability.

Experimental Results and Analysis

The theoretical derivations were validated through extensive Monte Carlo simulations. For norm estimation, $10^6$ samples from $\alpha$-stable distributions were used to evaluate bias and variance across sample sizes ranging from $n=5$ to $n=1000$.

Efficiency and Bias Correction

A key finding is that 1-bit coding is surprisingly efficient. For $\alpha=1$, the optimal 1-bit variance is only approximately 20% higher than the variance achievable with infinite-bit information. The Bartlett correction proves essential for practical applications; without it, the MLE is significantly biased when the measurement budget is small.

Mean Square Error (MSE) of the corrected MLE compared to theoretical variance across different sample sizes and parameters.

As shown in the figure above, the empirical Mean Square Error (MSE) of the corrected estimator (red line) aligns closely with the theoretical asymptotic variance (blue dash-dot line) even at low sample sizes, whereas the standard MLE (black dashed line) exhibits substantial error.

Integration with Compressed Sensing

The estimator was integrated into a "one-scan" 1-bit CS algorithm. In tests using synthetic sparse signals ($N=1000, K=20$), the algorithm successfully estimated signal sparsity on the fly. The recovery performance using these estimates was nearly identical to results obtained with perfectly known sparsity, requiring approximately $M = 9K \log N$ measurements for accurate reconstruction.

Conclusion and Future Directions

This work establishes that accurate $l_\alpha$ norm estimation is possible from extremely quantized measurements. While the 1-bit scheme is sensitive to the initial threshold choice, multi-bit extensions provide a more robust alternative. Future research may focus on optimizing threshold selection algorithms, reducing the computational overhead of multi-bit MLE solvers, and extending these techniques to dynamic or time-varying signal environments.

Summary updated

Abstract

We develop efficient binary (i.e., 1-bit) and multi-bit coding schemes for estimating the scale parameter of α-stable distributions. The work is motivated by the recent work on one scan 1-bit compressed sensing (sparse signal recovery) [12] using α-stable random projections, which requires estimating of the scale parameter at bits-level. Our technique can be naturally applied to data stream computations for estimating the α-th frequency moment. In fact, the method applies to the general scale family of distributions, not limited to α-stable distributions.
BibTeX
@inproceedings{li2017binary,
  author = {Ping Li},
  title = {{Binary and Multi-Bit Coding for Stable Random Projections}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2017},
}
Figure