Introduction
Compressive Sensing (CS) has revolutionized signal processing by enabling the recovery of high-dimensional signals from a limited number of linear measurements. In many practical hardware implementations, such as high-speed analog-to-digital converters, we encounter 1-bit Compressive Sensing. In this regime, only the sign of each measurement is recorded, discarding magnitude information entirely. While 1-bit CS is hardware-efficient and robust to certain non-linearities, it presents significant mathematical challenges for signal reconstruction.
Traditional 1-bit CS theory relies heavily on unstructured, i.i.d. Gaussian sensing matrices. However, these matrices are computationally expensive for high-dimensional data, requiring $O(mn)$ operations and massive memory storage. Furthermore, traditional methods assume signals are sparse in a fixed basis, an assumption often outperformed by modern generative priors (e.g., GANs or VAEs). This paper bridges these gaps by providing the first theoretical recovery guarantees for 1-bit CS using structured partial Gaussian circulant matrices combined with generative models.
Methodology and Matrix Design
The authors propose a recovery framework based on constrained correlation-based optimization. The goal is to find a vector within the range of a generative model $G$ that maximizes correlation with the observed 1-bit measurements.
Structured Sensing Matrices
To overcome the computational bottlenecks of Gaussian matrices, the authors utilize partial Gaussian circulant matrices. These matrices allow for fast signal processing via the Fast Fourier Transform (FFT), reducing complexity from $O(mn)$ to $O(n \log n)$. To ensure the mathematical properties required for recovery, the sensing matrix is designed as a product of a partial circulant matrix and a random diagonal matrix (random column sign flips). This pre-processing step ensures the signal satisfies an $\ell_\infty$-norm bound, which is critical for handling the dependencies inherent in circulant structures.
Generative Priors
Instead of the classical sparsity assumption, the signal is assumed to lie in the range of an $L$-Lipschitz continuous generative model $G: \mathbb{R}^k \to \mathbb{R}^n$, where $k \ll n$. This allows the recovery process to leverage the learned manifold of natural signals, such as images, leading to better performance at lower sampling rates.
Theoretical Contributions
The core contribution of this work is the proof that structured matrices can match the performance of unstructured ones. The authors establish that for a generative model with a $k$-dimensional input, the number of measurements $m$ required for accurate recovery is:
$$m = O\left(\frac{k \log L}{\epsilon^2}\right)$$
This sample complexity is order-optimal and demonstrates that there is no "theoretical penalty" for using computationally efficient circulant matrices instead of standard Gaussian matrices. Furthermore, the recovery scheme is shown to be robust against various types of degradations, including:
- Random bit flips (measurement noise).
- Noise added before quantization (probit/logit models).
- Adversarial corruptions.
Experimental Validation
The authors validated their theoretical findings using the MNIST and CelebA datasets, comparing their approach against traditional sparsity-based methods like 1-bit Lasso and Binary Iterative Hard Thresholding (BIHT).
Key Findings:
- Computational Efficiency: On the CelebA dataset ($n=12,288$), the use of circulant matrices resulted in a 2x to 4x speedup per iteration compared to i.i.d. Gaussian matrices, significantly reducing the time required for high-resolution reconstruction.
- Reconstruction Quality: Generative priors demonstrated superior performance at extremely low measurement counts. On MNIST, the proposed method achieved recognizable reconstructions with as few as 200 measurements, a regime where sparsity-based methods typically fail.
- Robustness: The experiments confirmed the theoretical prediction that the correlation-based optimization remains stable even in the presence of flipped bits and adversarial noise.
Conclusion and Future Work
This research provides a rigorous foundation for using structured matrices in 1-bit compressive sensing with generative priors. By proving that partial Gaussian circulant matrices achieve optimal sample complexity, the authors enable faster and more memory-efficient recovery for real-world applications.
Future research directions include relaxing the $\ell_\infty$ norm assumption on the signal and extending the theory to uniform recovery, where a single sensing matrix can guarantee the recovery of all signals in the generator's range. Additionally, exploring pure Fourier 1-bit CS—where sign flips cannot be manually introduced—remains a significant challenge for fields like medical imaging.
Summary updated