Just Least Squares: Binary Compressive Sampling with Low Generative Intrinsic Dimension
This work addresses signal recovery in compressive sensing for applications like imaging or communications, but it is incremental as it builds on existing generative prior frameworks with a specific decoder.
The paper tackles the problem of recovering signals from noisy binary measurements under a low generative intrinsic dimension assumption, proposing a least squares decoder that achieves an estimation error of O(√(k log(Ln)/m)) with m ≥ O(k log(Ln)), as validated by simulations showing robustness to noise and sign flips.
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\rightarrow\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\geq \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.