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

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 : R-k -> R-n, k << 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 C root (k log(Ln))/(m ) as long as m >= C(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.

Automated summary

In this paper, the recovery of n-dimensional signals from m binary measurements corrupted by noises and sign flips is considered. It is assumed that the target signals have low generative intrinsic dimension. A least square decoder is proposed and its performance is proved. Through extensive numerical simulations and comparisons, it is demonstrated that the least square decoder is robust to noise and sign flips.