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:
- 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.
- 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.
- 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.
- 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