Recovery Guarantees for Posterior Sampling of One-Bit Compressed Sensing

arXiv:2610.11834 · cs.LG, cs.IT, math.IT · Submitted 2026-10-08 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom, and with me are Jane, Lu, senior AI researcher at Tsinghua, Meng, lead engineer at a mysterious AI startup and Lalam, the in-house Large Language Model.

Jane: Today's paper: "Recovery Guarantees for Posterior Sampling of One-Bit Compressed Sensing".

Tom: The gist: The authors prove that posterior sampling achieves accurate recovery for noisy one-bit compressed sensing when measurement counts scale with the logarithm of the approximate covering number,

Jane: First, who's behind it and why it matters.

Paper summary: Jane: So, looking at "Recovery Guarantees for Posterior Sampling of One-Bit Compressed Sensing" by Jing Ma and Yujia Wu and Zhaoqiang Liu, what’s the big picture here?

Tom: It really boils down to this: we have a precise way to measure the complexity of the prior distribution using its approximate covering number <ref:2610.11834#pg2>. This complexity dictates exactly how many measurements you need for reliable recovery in one-bit compressed sensing <ref:2610.11834#pg3>.

Lu: It’s about establishing a nearly matching information-theoretic necessary condition, which is something we needed for this specific setting <ref:2610.11834#pg3>.

Meng: For the practical person, it means we can use diffusion priors with an algorithm like PnP-OneBit to get good results on data like FFHQ or ImageNet, even when compression is really aggressive <ref:2610.11834#pg3>.

Lalam: And from a culture perspective, if this helps us understand the limits of what we can recover with limited measurements in compressed sensing, it gives us a better framework for designing next-generation signal processing models <ref:2610.11834#pg2>.

Tom: So, the paper shows that reliable recovery under severe nonlinear quantization can be precisely characterized by the high probability geometric complexity of the signal prior <ref:2610.11834#pg2>. That’s what they proved.

Conclusion: Tom: So we're wrapping up this deep dive into "Recovery Guarantees for Posterior Sampling of One-Bit Compressed Sensing."

Jane: It’s about how much data you actually need to get a signal back when your measurements are super noisy, one bit at a time.

Lu: The authors are basically showing that the complexity of the prior distribution—specifically this approximate covering number—is the real limit here.

Meng: So, instead of just guessing how much data you need, they give you a hard number based on the shape of your data.

Lalam: It establishes a necessary condition for recovery; without that much information complexity, you just can't reliably recover the signal.

Tom: It’s like saying this is the minimum cost to get a reliable result in this specific kind of compression.

Jane: And they did this by looking at both the best possible upper bound and a lower bound for how many measurements are required.

Lu: The key result is that that approximate covering number term shows up as unavoidable in any reliable recovery method you try to use.

Meng: For practical terms, it means if your prior distribution has high geometric complexity, you need more measurements to be sure you get the right signal back.

Lalam: This shifts the focus from just making algorithms work to understanding the fundamental information limits of this sensing problem.

Tom: It’s a really clean way of characterizing recovery under these kinds of severe nonlinear quantization issues.

Jane: And they even showed how a specific algorithm, PnP-OneBit, actually performs well on big image datasets like FFHQ and ImageNet with this framework.

Lu: That practical validation is important because it connects the theory to what we can actually build in practice with diffusion priors.

Meng: So, the world changes because now we have a clear way to predict if our limited sensing setup will fail before we even start the experiment.

Lalam: This pushes us toward designing sensing schemes that match the inherent geometric complexity of the data they are trying to capture.

University of Electronic Science and Technology of China

cs.LG, cs.IT, math.IT

Submitted: 2026-10-08

Updated: 2026-10-12

Comments: Accepted to NeurIPS 2026

Code: https://github.com/Dugehude/pnp-onebit

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 87/100

The gist: The gist: The authors prove that posterior sampling achieves accurate recovery for noisy one-bit compressed sensing when measurement counts scale with the logarithm of the approximate covering

Key concepts

Approximate Covering Number: This is a geometric measure used to quantify the complexity or 'size' of a high probability region in signal space. In this context, it helps determine how many distinct signal patterns are needed to cover the relevant area of possibilities, which directly relates to the required sample size for reliable recovery.
Posterior Sampling: This is a method used to estimate the true underlying signal distribution by sampling from a posterior distribution. The authors extend this technique from continuous measurements to the challenging setting of noisy one-bit compressed sensing, analyzing its performance under various conditions.
Sample Complexity: This refers to the minimum number of measurements required for a reliable recovery method to succeed. The paper establishes bounds (both upper and lower) on this complexity, showing that it is fundamentally linked to the geometric complexity of the signal's prior distribution.
Noisy One-Bit Compressed Sensing: This scenario involves reconstructing a signal from extremely limited measurements where each measurement is quantized into only one bit. The paper analyzes recovery guarantees in this severe form of compression, considering how noise and quantization affect the ability to recover the original signal.

Summary

The gist: The authors prove that posterior sampling achieves accurate recovery for noisy one-bit compressed sensing when measurement counts scale with the logarithm of the approximate covering number, establishing this as a necessary information-theoretic lower bound.

Theoretical Framework and Complexity Measures

The paper studies the sample complexity of noisy one-bit compressed sensing for signals drawn from an arbitrary data prior distribution on the unit sphere, characterizing this complexity through the approximate covering number of a high probability region The central question is how to characterize the sample complexity of reliable recovery from noisy one-bit measurements in terms of the prior distribution The authors extend the distributional posterior sampling framework from continuous linear measurements to the noisy one-bit setting, analyzing recovery guarantees under prior mismatch and establishing a nearly matching information-theoretic necessary condition in the leading prior complexity term

Key Results on Sample Complexity Bounds

The main results establish both an upper bound and a lower bound for the sample complexity required for reliable signal recovery

** Upper Bound:**

The authors derive an upper bound on the sample complexity with Gaussian measurement matrices, showing that for geodesic recovery accuracy η, the condition is roughly proportional to log Covη,δ(R) This bound is robust to mismatch between the learned prior distribution and the true signal distribution when they are sufficiently close in Wasserstein distance

** Lower Bound:**

The authors derive a nearly matching lower bound on the sample complexity required by any reliable recovery method, showing that the approximate covering number in the upper bound is unavoidable This demonstrates that the approximate covering number is the correct distributional complexity measure for one-bit compressed sensing with arbitrary data priors

Analysis of Recovery Guarantees

The proof of Theorem 3.1 relies on several lemmas to establish the recovery guarantee

** Lemma 3.2:**

This lemma shows that geodesic separation is transformed by the one-bit channel into a gap in expected Hamming disagreement, quantified by ∆σ(c, η)

** Lemma 3.3:**

This lemma provides a one-bit near–far test lemma, showing that the testing error decays exponentially with the number of measurements m

** Lemma 3.5:**

This lemma controls the probability loss under Wasserstein infinity mismatch through a Rényi type stability argument

Practical Implementation and Experimental Validation

To approximate the ideal posterior sampling process, the authors instantiate posterior sampling through a plug-and-play algorithm called PnP-OneBit using diffusion priors This method utilizes a split Gibbs sampler (SGS) to construct an effective posterior sampling algorithm

** Algorithm 2:**

The detailed PnP-OneBit algorithm involves alternating sampling between the data fidelity term and the prior term using a pretrained diffusion model as a plug-and-play prior

The experimental results on FFHQ and ImageNet datasets demonstrate the effectiveness of this proposed approach PnP-OneBit consistently achieves great reconstruction performance on all evaluated metrics, even at severe compression ratios

Conclusion

Overall, the results show that reliable recovery under severe nonlinear quantization can be precisely characterized by the high probability geometric complexity of the signal prior The paper concludes that reliable recovery is precisely characterized by the high probability geometric complexity of the signal prior.

--- Page 5 ---

The authors study noisy one-bit compressed sensing for signals drawn from arbitrary data prior distributions on the sphere, characterizing this complexity through the approximate covering number of a high probability region The central question is how to characterize the sample complexity of reliable recovery from noisy one-bit measurements in terms of the prior distribution

Theoretical Framework and Complexity Measures

Conclusion

Overall, the results show that reliable recovery under severe nonlinear quantization can be precisely characterized by the high probability geometric complexity of the signal prior.

Improvements for AI systems

Improved posterior sampling for noisy one-bit compressed sensing: The system can achieve accurate recovery with high probability by scaling measurements with the logarithm of the approximate covering number, which is characterized as the correct distributional complexity measure for one-bit compressed sensing with arbitrary data priors.
Robustness to learned prior mismatch: The system remains reliable even when the learned prior distribution is sufficiently close to the true signal distribution in Wasserstein distance, quantified by controlling model mismatch using a Rényi type stability argument.
Plug-and-play reconstruction for diffusion priors: The system can be instantiated using a plug-and-play algorithm with diffusion priors, specifically leveraging pretrained generative models to approximate the posterior sampling process via an alternating sampling strategy to reconstruct the signal from one-bit observations.

Abstract

We study the sample complexity of noisy one-bit compressed sensing for signals drawn from a prior distribution. By characterizing the effective distributional complexity of the prior via its approximate covering number, we prove that posterior sampling achieves accurate recovery with high probability when the number of measurements scales with the logarithm of the approximate covering number, up to a one-bit separation gap factor. This upper bound is robust to learned prior mismatch. Specifically, we show that posterior sampling with an approximate prior remains reliable, provided that the learned prior distribution is sufficiently close to the true signal distribution in Wasserstein distance. In addition, we establish a sample complexity lower bound for any reliable method of noisy one-bit compressed sensing, showing that our upper bound is nearly matched in its main prior dependent term. To approximate the ideal posterior sampling process for real world scenarios, we instantiate posterior sampling through a plug-and-play algorithm with diffusion priors. Experiments on the FFHQ and ImageNet datasets demonstrate the effectiveness of our proposed approach.