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

Abstract

We study the robust one-bit compressed sensing problem whose goal is to design an algorithm that faithfully recovers any sparse target vector _0R^d uniformly from m quantized noisy measurements. Under the assumption that the measurements are sub-Gaussian, to recover any k-sparse _0 (k d) uniformly up to an error with high probability, the best known computationally tractable algorithm requiresHere, an algorithm is ``computationally tractable'' if it has provable convergence guarantees. The notation O() omits a logarithm factor of ^-1. mO(k d/^4). In this paper, we consider a new framework for the one-bit sensing problem where the sparsity is implicitly enforced via mapping a low dimensional representation x_0 through a known n-layer ReLU generative network G:R^kR^d. Such a framework poses low-dimensional priors on _0 without a known basis. We propose to recover the target G(x_0) via an unconstrained empirical risk minimization (ERM) problem under a much weaker sub-exponential measurement assumption. For such a problem, we establish a joint statistical and computational analysis. In particular, we prove that the ERM estimator in this new framework achieves an improved statistical rate of m=O (kn d /^2) recovering any G(x_0) uniformly up to an error . Moreover, from the lens of computation, we prove that under proper conditions on the ReLU weights, our proposed empirical risk, despite non-convexity, has no stationary point outside of small neighborhoods around the true representation x_0 and its negative multiple. Furthermore, we show that the global minimizer of the empirical risk stays within the neighborhood around x_0 rather than its negative multiple. Our analysis sheds some light on the possibility of inverting a deep generative model under partial and quantized measurements, complementing the recent success of using deep generative models for inverse problems.

Tasks

Reproductions