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

arXiv: https://arxiv.org/abs/2108.03570 · HTML: https://mlsanity.com/paper/2108.03570/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 64 references that are in the map.
- First posted on arXiv 8 Aug 2021.

## Builds on (most cited first, 21 of 21)

- [Deep Learning Face Attributes in the Wild](https://mlsanity.com/paper/1411.7766/) (2014)
- [Compressed Sensing using Generative Models](https://mlsanity.com/paper/1703.03208/) (2017)
- [Deep Learning Techniques for Inverse Problems in Imaging](https://mlsanity.com/paper/2005.06001/) (2020)
- [Deep Decoder: Concise Image Representations from Untrained Non-convolutional Networks](https://mlsanity.com/paper/1810.03982/) (2018)
- [Phase Retrieval Under a Generative Prior](https://mlsanity.com/paper/1807.04261/) (2018)
- [Intermediate Layer Optimization for Inverse Problems using Deep Generative Models](https://mlsanity.com/paper/2102.07364/) (2021)
- [Compressed Sensing with Deep Image Prior and Learned Regularization](https://mlsanity.com/paper/1806.06438/) (2018)
- [Robust Compressed Sensing using Generative Models](https://mlsanity.com/paper/2006.09461/) (2020)
- [An Introductory Guide to Fano's Inequality with Applications in Statistical Estimation](https://mlsanity.com/paper/1901.00555/) (2019)
- [Information-Theoretic Lower Bounds for Compressive Sensing with Generative Models](https://mlsanity.com/paper/1908.10744/) (2019)
- [Sample Complexity Bounds for 1-bit Compressive Sensing and Binary Stable Embeddings with Generative Priors](https://mlsanity.com/paper/2002.01697/) (2020)
- [The Generalized Lasso with Nonlinear Observations and Generative Priors](https://mlsanity.com/paper/2006.12415/) (2020)
- [Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors](https://mlsanity.com/paper/2106.15358/) (2021)
- [One-bit compressive sensing with norm estimation](https://mlsanity.com/paper/1404.6853/) (2014)
- [Global Guarantees for Blind Demodulation with Generative Priors](https://mlsanity.com/paper/1905.12576/) (2019)
- [Robust One-Bit Recovery via ReLU Generative Networks: Near-Optimal Statistical Rate and Global Landscape Analysis](https://mlsanity.com/paper/1908.05368/) (2019)
- [Binary Embedding: Fundamental Limits and Fast Algorithm](https://mlsanity.com/paper/1502.05746/) (2015)
- [On Binary Embedding using Circulant Matrices](https://mlsanity.com/paper/1511.06480/) (2015)
- [Robust one-bit compressed sensing with partial circulant matrices](https://mlsanity.com/paper/1812.06719/) (2018)
- [Near-Optimal Sample Complexity Bounds for Circulant Binary Embedding](https://mlsanity.com/paper/1603.03178/) (2016)
- [Fast binary embeddings with Gaussian circulant matrices: improved bounds](https://mlsanity.com/paper/1608.06498/) (2016)

## Built on by (most cited first, 7 of 7)

- [Generative Principal Component Analysis](https://mlsanity.com/paper/2203.09693/) (2022)
- [Non-Iterative Recovery from Nonlinear Observations using Generative Models](https://mlsanity.com/paper/2205.15749/) (2022)
- [Integrating Intermediate Layer Optimization and Projected Gradient Descent for Solving Inverse Problems with Diffusion Models](https://mlsanity.com/paper/2505.20789/) (2025)
- [Projected Gradient Descent Algorithms for Solving Nonlinear Inverse Problems with Generative Priors](https://mlsanity.com/paper/2209.10093/) (2022)
- [Learning Single Index Models with Diffusion Priors](https://mlsanity.com/paper/2505.21135/) (2025)
- [Image Restoration via Diffusion Models with Dynamic Resolution](https://mlsanity.com/paper/2605.14267/) (2026)
- [One-bit Compressed Sensing using Generative Models](https://mlsanity.com/paper/2502.12762/) (2025)

## Abstract (arXiv)

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 randomly signed partial Gaussian circulant matrices and generative models. Under suitable assumptions, we match guarantees that were previously only known to hold for i.i.d.~Gaussian matrices that require significantly more computation. We make use of a practical iterative algorithm, and perform numerical experiments on image datasets to corroborate our theoretical results.