# Sample Complexity Bounds for 1-bit Compressive Sensing and Binary Stable Embeddings with Generative Priors

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Feb 2020.

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

- [Robust Compressed Sensing MRI with Deep Generative Priors](https://mlsanity.com/paper/2108.01368/) (2021)
- [Instance-Optimal Compressed Sensing via Posterior Sampling](https://mlsanity.com/paper/2106.11438/) (2021)
- [Theoretical Perspectives on Deep Learning Methods in Inverse Problems](https://mlsanity.com/paper/2206.14373/) (2022)
- [Quantized Compressed Sensing with Score-based Generative Models](https://mlsanity.com/paper/2211.13006/) (2022)
- [Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors](https://mlsanity.com/paper/2106.15358/) (2021)
- [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)
- [Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors](https://mlsanity.com/paper/2108.03570/) (2021)
- [Misspecified Phase Retrieval with Generative Priors](https://mlsanity.com/paper/2210.05571/) (2022)
- [A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing](https://mlsanity.com/paper/2310.03758/) (2023)
- [Projected Gradient Descent Algorithms for Solving Nonlinear Inverse Problems with Generative Priors](https://mlsanity.com/paper/2209.10093/) (2022)
- [QCM-SGM+: Improved Quantized Compressed Sensing With Score-Based Generative Models](https://mlsanity.com/paper/2302.00919/) (2023)
- [Solving Quadratic Systems with Full-Rank Matrices Using Sparse or Generative Priors](https://mlsanity.com/paper/2309.09032/) (2023)
- [Equivariant Priors for Compressed Sensing with Unknown Orientation](https://mlsanity.com/paper/2206.14069/) (2022)
- [Generalized Eigenvalue Problems with Generative Priors](https://mlsanity.com/paper/2411.01326/) (2024)
- [Just Least Squares: Binary Compressive Sampling with Low Generative Intrinsic Dimension](https://mlsanity.com/paper/2111.14486/) (2021)
- [Optimizing Sampling Patterns for Compressed Sensing MRI with Diffusion Generative Models](https://mlsanity.com/paper/2306.03284/) (2023)
- [Learning Single Index Models with Diffusion Priors](https://mlsanity.com/paper/2505.21135/) (2025)
- [One-bit Compressed Sensing using Generative Models](https://mlsanity.com/paper/2502.12762/) (2025)
- [Diffusion Model Based Signal Recovery Under 1-Bit Quantization](https://mlsanity.com/paper/2511.12471/) (2025)
- [Position: AI for Science Should Treat Measurement-to-Dataset Pipelines as Inference Components](https://mlsanity.com/paper/2605.24558/) (2026)

## Abstract (arXiv)

The goal of standard 1-bit compressive sensing is to accurately recover an unknown sparse vector from binary-valued measurements, each indicating the sign of a linear function of the vector. Motivated by recent advances in compressive sensing with generative models, where a generative modeling assumption replaces the usual sparsity assumption, we study the problem of 1-bit compressive sensing with generative models. We first consider noiseless 1-bit measurements, and provide sample complexity bounds for approximate recovery under i.i.d.~Gaussian measurements and a Lipschitz continuous generative prior, as well as a near-matching algorithm-independent lower bound. Moreover, we demonstrate that the Binary ε-Stable Embedding property, which characterizes the robustness of the reconstruction to measurement errors and noise, also holds for 1-bit compressive sensing with Lipschitz continuous generative models with sufficiently many Gaussian measurements. In addition, we apply our results to neural network generative models, and provide a proof-of-concept numerical experiment demonstrating significant improvements over sparsity-based approaches.