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

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 63 references that are in the map.
- First posted on arXiv 29 Nov 2021.

## Builds on (most cited first, 17 of 17)

- [Auto-Encoding Variational Bayes](https://mlsanity.com/paper/1312.6114/) (2013)
- [Variational Inference with Normalizing Flows](https://mlsanity.com/paper/1505.05770/) (2015)
- [Deep Image Prior](https://mlsanity.com/paper/1711.10925/) (2017)
- [Compressed Sensing using Generative Models](https://mlsanity.com/paper/1703.03208/) (2017)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Phase Retrieval Under a Generative Prior](https://mlsanity.com/paper/1807.04261/) (2018)
- [Deep Compressed Sensing](https://mlsanity.com/paper/1905.06723/) (2019)
- [On the Optimal Memorization Power of ReLU Neural Networks](https://mlsanity.com/paper/2110.03187/) (2021)
- [Nonlinear Approximation via Compositions](https://mlsanity.com/paper/1902.10170/) (2019)
- [An error analysis of generative adversarial networks for learning distributions](https://mlsanity.com/paper/2105.13010/) (2021)
- [Information-Theoretic Lower Bounds for Compressive Sensing with Generative Models](https://mlsanity.com/paper/1908.10744/) (2019)
- [Sample Complexity Bounds for 1-bit Compressive Sensing and Binary Stable Embeddings with Generative Priors](https://mlsanity.com/paper/2002.01697/) (2020)
- [A Provably Convergent Scheme for Compressive Sensing under Random Generative Priors](https://mlsanity.com/paper/1812.04176/) (2018)
- [The Generalized Lasso with Nonlinear Observations and Generative Priors](https://mlsanity.com/paper/2006.12415/) (2020)
- [L1-Regularized Least Squares for Support Recovery of High Dimensional Single Index Models with Gaussian Designs](https://mlsanity.com/paper/1511.08102/) (2015)
- [An Approach to One-Bit Compressed Sensing Based on Probably Approximately Correct Learning Theory](https://mlsanity.com/paper/1710.07973/) (2017)
- [Pinball Loss Minimization for One-bit Compressive Sensing: Convex Models and Algorithms](https://mlsanity.com/paper/1505.03898/) (2015)

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

- [Theoretical Perspectives on Deep Learning Methods in Inverse Problems](https://mlsanity.com/paper/2206.14373/) (2022)
- [A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing](https://mlsanity.com/paper/2310.03758/) (2023)

## Abstract (arXiv)

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: ℝkrightarrowℝn, kll 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 O (√fracklog (Ln)m) as long as m≥ O( klog (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.