Just Least Squares: Binary Compressive Sampling with Low Generative Intrinsic Dimension

Abstract

In this paper, we consider recovering $n$ dimensional signals from $m$ binary measurements corrupted by noises and sign flips under the assumption that the target signals have low generative intrinsic dimension, i.e., the target signals can be approximately generated via an $L$-Lipschitz generator $G:{\mathbb{R}}^k\to {\mathbb{R}}^n,k\ll n$. Although the binary measurements model is highly nonlinear, we propose a least square decoder and prove that, up to a constant $c$, with high probability, the least square decoder achieves a sharp estimation error $\mathcal{O}(\sqrt{\frac{k\log (Ln)}{m}})$ as long as $m\ge \mathcal{O}(k\log (Ln))$. Extensive numerical simulations and comparisons with state-of-the-art methods demonstrated the least square decoder is robust to noise and sign flips, as indicated by our theory. By constructing a ReLU network with properly chosen depth and width, we verify the (approximately) deep generative prior, which is of independent interest.

References in corpus (15)

• Auto-Encoding Variational Bayes
• Variational Inference with Normalizing Flows
• Compressed Sensing using Generative Models
• Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks
• Regime Change: Bit-Depth versus Measurement-Rate in Compressive Sensing
• Nonlinear Approximation via Compositions
• Quantized Iterative Hard Thresholding: Bridging 1-bit and High-Resolution Quantized Compressed Sensing
• Deep Compressed Sensing
• A Provably Convergent Scheme for Compressive Sensing under Random Generative Priors
• Phase Retrieval Under a Generative Prior
• An error analysis of generative adversarial networks for learning distributions
• The Generalized Lasso with Nonlinear Observations and Generative Priors
• Robust One-Bit Recovery via ReLU Generative Networks: Near-Optimal Statistical Rate and Global Landscape Analysis
• On the Optimal Memorization Power of ReLU Neural Networks
• Robust Decoding from Binary Measurements with Cardinality Constraint Least Squares