Near-Optimal Lower Bounds on One-Bit Compressed Sensing of Approximately Sparse Signals

What the math gives to ML

The paper establishes an information-theoretic resolution floor for recovering approximately sparse vectors after one-bit linear measurements: increasing ambient dimension or decoder capacity cannot overcome the loss caused by sign quantization at fixed measurement count. The transferable asset is the explicit scaling law between effective sparsity, number of binary measurements, and achievable uniform Euclidean error, including the continuous interpolation between exact sparsity and ℓ1-type approximate sparsity. In neural networks, this can become a principled bit-budget rule and an impossibility-aware training target for binary latent bottlenecks, sign-activated encoders, and compressed communication layers rather than relying on arbitrary latent widths.