Universal 1-Bit Compressive Sensing for Bounded Dynamic Range Signals

Sidhant Bansal, Arnab Bhattacharyya, Anamay Chaturvedi, Jonathan Scarlett

Abstract

This paper investigates the fundamental limits of "universal" 1-bit compressive sensing—the task of recovering the support of sparse signals using only the signs of linear measurements. By introducing the dynamic range $R$ as a complexity metric, the authors bridge the theoretical gap between binary and general sparse signals. They prove that for signals with a bounded dynamic range, the number of measurements required scales with $k^{3/2}$ (where $k$ is sparsity), establishing a new lower bound for Gaussian matrices and a matching upper bound that confirms $k^{3/2}$ as a fundamental bottleneck in universal recovery.

Introduction

Compressive Sensing (CS) has revolutionized signal processing by demonstrating that sparse signals can be recovered from far fewer measurements than the Nyquist-Shannon theorem suggests. 1-bit CS represents an extreme quantization limit where only the sign of each measurement is recorded. This model is particularly relevant for high-speed hardware where low-resolution quantizers (comparators) are more efficient than high-precision analog-to-digital converters.

A critical distinction in CS theory is between "for-each" and "for-all" (universal) guarantees. In a universal guarantee, a single measurement matrix must successfully recover every possible signal in a given class. Previous research revealed a significant discrepancy in universal 1-bit CS:

  • Arbitrary $k$-sparse signals require approximately $O(k^2)$ measurements.
  • Binary $k$-sparse signals (where non-zero entries are 1) require only $O(k^{3/2})$ measurements.

This paper addresses the middle ground by analyzing signals with a bounded dynamic range $R$—the ratio between the largest and smallest non-zero entries. The authors seek to determine how signal diversity influences the measurement complexity required for universal support recovery.

Methodology

The study employs high-dimensional probability and information theory to derive scaling laws for measurement matrices. The core analytical framework involves several key components:

  1. Vector Balancing Reduction: The authors reduce the support recovery problem to a "vector balancing" challenge. Support recovery fails if a measurement matrix cannot distinguish between two signals with slightly different supports. This occurs if the rows of the matrix are not sufficiently "balanced" to detect the variation in signal values.
  2. De Caen’s Inequality: To establish the lower bound, the researchers utilize de Caen’s inequality to estimate the probability that a random Gaussian matrix fails to be balanced for at least one pair of supports within the signal class.
  3. Small Ball Probabilities: Gaussian density estimates are used to analyze the likelihood of the sum of random variables falling within a small interval around zero, which corresponds to a failure in measurement sensitivity.
  4. Rademacher Analysis: The findings are extended from continuous Gaussian matrices to discrete Rademacher matrices (entries of $\pm 1$), demonstrating that the $k^{3/2}$ bottleneck is a property of the sensing task rather than the specific distribution of the matrix.

Key Results and Insights

The $k^{3/2}$ Fundamental Barrier

The paper confirms that the $k^{3/2}$ scaling is not unique to binary signals but is a fundamental bottleneck for universal recovery using i.i.d. Gaussian measurements. This result effectively bridges the gap between the $k^{3/2}$ complexity of binary signals and the $k^2$ complexity of general signals.

Dynamic Range as a Complexity Metric

The research identifies that the number of measurements scales linearly with the dynamic range $R$. As the diversity of signal values increases (higher $R$), the "for-all" guarantee becomes increasingly difficult to satisfy. Specifically:

  • Lower Bound: For i.i.d. Gaussian matrices, the number of measurements $m$ must satisfy $m = \Omega(\tilde{R}k^{3/2} + k \log(n/k))$.
  • Upper Bound: The authors derive a near-matching upper bound of $O(Rk^{3/2} \log n)$, utilizing existing results from approximate recovery literature.

The Price of Universality

The results highlight the stark difference between "for-each" and "for-all" recovery. While "for-each" recovery (where a matrix works for a specific signal with high probability) only requires $O(k \log n)$ measurements, the requirement for a single matrix to work for all signals simultaneously drives the complexity to $k^{3/2}$. This jump is attributed to the geometric intuition that support recovery fails if signal components "cancel out" too frequently; bounding the dynamic range $R$ limits these extreme cancellations.

Conclusion and Future Work

This work provides a rigorous theoretical foundation for understanding the limits of 1-bit compressive sensing. By showing that Rademacher matrices also face the $\Omega(k^{3/2})$ requirement, the authors demonstrate the robustness of this limit across different sensing environments.

However, several avenues for future research remain:

  • Non-I.I.D. Matrices: It is currently unknown if structured or non-i.i.d. matrices could bypass the $k^{3/2}$ barrier.
  • Tightness of $R$: While the $k$ scaling is likely tight, the linear dependence on $R$ may be improvable, with some regimes potentially requiring $R^2$.
  • Algorithmic Efficiency: The current work focuses on information-theoretic limits. Future studies should investigate whether computationally efficient algorithms can achieve these theoretical bounds in practice.

Summary updated

Abstract

A universal 1-bit compressive sensing (CS) scheme consists of a measurement matrix A such that for all signals x belonging to a particular class, x can be approximately recovered from sign(Ax). 1-bit CS models extreme quantization effects where only one bit of information is revealed per measurement. We focus on universal support recovery for 1-bit CS in the case of sparse signals with bounded dynamic range. Specifically, a vector x ∈ℝ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> is said to have sparsity k if it has at most k nonzero entries and dynamic range R if the ratio between its largest and smallest nonzero entries is at most R in magnitude. Our main result shows that if the entries of the measurement matrix Ax are i.i.d. Gaussians, then the number of measurements needs to be ${{\tilde \Omega }}\left({R{k^{3/2}}}\right)$ to recover the support of k-sparse signals with dynamic range R using 1-bit CS. This contrasts with the known lower bound of ${{\tilde \Omega }}\left({{k^2}\log n}\right)$ for the number of measurements to recover the support of arbitrary k-sparse signals. In broad scaling regimes of interest, our lower bounds match upper bounds implicit in prior works up to logarithmic factors.
BibTeX
@inproceedings{bansal2022universal,
  author = {Sidhant Bansal and Arnab Bhattacharyya and Anamay Chaturvedi and Jonathan Scarlett},
  title = {{Universal 1-Bit Compressive Sensing for Bounded Dynamic Range Signals}},
  booktitle = {ISIT},
  year = {2022},
  url = {https://openreview.net/forum?id=wgywMJlOcn},
}
Figure