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

2021/11/29 by Yuling Jiao, Jiao, Yuling, Dingwei Li +7
Computer Science · Engineering · Mathematics · #Mathematical Analysis and Transform Methods #Microwave Imaging and Scattering Analysis #Sparse and Compressive Sensing Techniques #cs.LG #eess.SP #stat.ML

paper · pdf · doi:10.48550/arxiv.2111.14486

arxiv created 2021/11/29 · arxiv updated 2021/11/30

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: ℝ^k→ℝⁿ, 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 O (√((klog (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.

Citations

• Auto-Encoding Variational Bayes
• Fractal Geometry: Mathematical Foundations and Applications.
• Gradient-based learning applied to document recognition
• Compressed Sensing using Generative Models
• Deep Compressed Sensing
• On the Optimal Memorization Power of ReLU Neural Networks

Related

• Robust Decoding from Binary Measurements with Cardinality Constraint Least Squares
• Information-Theoretic Lower Bounds for Compressive Sensing with Generative Models
• Robust Decoding from 1-Bit Compressive Sampling with Least Squares
• The Generalized Lasso with Nonlinear Observations and Generative Priors
• Compressed Sensing using Generative Models