# Robust One-Bit Recovery via ReLU Generative Networks: Near-Optimal Statistical Rate and Global Landscape Analysis

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Aug 2019.

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

- [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)
- [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)
- [Over-the-Air Design of GAN Training for mmWave MIMO Channel Estimation](https://mlsanity.com/paper/2205.12445/) (2022)
- [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)

## Abstract (arXiv)

We study the robust one-bit compressed sensing problem whose goal is to design an algorithm that faithfully recovers any sparse target vector θ0∈ℝd textituniformly via m quantized noisy measurements. Specifically, we consider a new framework for this problem where the sparsity is implicitly enforced via mapping a low dimensional representation x0 ∈ ℝk through a known n-layer ReLU generative network G:ℝkrightarrowℝd such that θ0 = G(x0). Such a framework poses low-dimensional priors on θ0 without a known sparsity basis. We propose to recover the target G(x0) solving an unconstrained empirical risk minimization (ERM). Under a weak textitsub-exponential measurement assumption, we establish a joint statistical and computational analysis. In particular, we prove that the ERM estimator in this new framework achieves a statistical rate of m=widetildeO(kn log d /varepsilon2) recovering any G(x0) uniformly up to an error varepsilon. When the network is shallow (i.e., n is small), we show this rate matches the information-theoretic lower bound up to logarithm factors of varepsilon-1. From the lens of computation, we prove that under proper conditions on the network weights, our proposed empirical risk, despite non-convexity, has no stationary point outside of small neighborhoods around the true representation x0 and its negative multiple; furthermore, we show that the global minimizer of the empirical risk stays within the neighborhood around x0 rather than its negative multiple under further assumptions on the network weights.