Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors

Zhaoqiang Liu, Subhroshekhar Ghosh, Jonathan Scarlett

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:

  1. 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.
  2. 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.
  3. 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

Abstract

In 1-bit compressive sensing, each measurement is quantized to a single bit, namely the sign of a linear function of an unknown vector, and the goal is to accurately recover the vector. While it is most popular to assume a standard Gaussian sensing matrix for 1-bit compressive sensing, using structured sensing matrices such as partial Gaussian circulant matrices is of significant practical importance due to their faster matrix operations. In this paper, we provide recovery guarantees for a correlation-based optimization algorithm for robust 1-bit compressive sensing with partial Gaussian circulant matrices (with random column sign flips) under a generative prior, where the signal to estimate is assumed to belong to the range of a Lipschitz continuous generative model with bounded inputs. Under suitable assumptions, we match guarantees that were previously only known to hold for i.i.d. Gaussian matrices that require significantly more computation.
BibTeX
@inproceedings{liu2021robust,
  author = {Zhaoqiang Liu and Subhroshekhar Ghosh and Jonathan Scarlett},
  title = {{Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors}},
  booktitle = {ITW},
  year = {2021},
  url = {https://openreview.net/forum?id=rO_-fxj1Dl9},
}
Figure