Robust One-Bit Recovery via ReLU Generative Networks: Near-Optimal 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 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 x_0 R^k through a known n-layer ReLU generative network G:R^kR^d such that _0 = G(x_0). Such a framework poses low-dimensional priors on _0 without a known sparsity basis. We propose to recover the target G(x_0) solving an unconstrained empirical risk minimization (ERM). Under a weak sub-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=O(kn d /^2) recovering any G(x_0) uniformly up to an error . 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 ^-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 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 under further assumptions on the network weights.

Tasks

Reproductions