Recovery Guarantees for Posterior Sampling of One-Bit Compressed Sensing

Jing Ma; Yujia Wu; Zhaoqiang Liu

cs.LGOct 8, 2026

Recovery Guarantees for Posterior Sampling of One-Bit Compressed Sensing

Authors: Jing Ma, Yujia Wu, Zhaoqiang Liu

Organizations: University of Electronic Science and Technology of China

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.

Figures & tables

Figure 1

Methods	$n/m=16$			$n/m=32$
Methods	PSNR $\uparrow$	SSIM $\uparrow$	LPIPS $\downarrow$	PSNR $\uparrow$	SSIM $\uparrow$	LPIPS $\downarrow$
DiffPIR	11.71 $\pm$ 1.26	0.30 $\pm$ .05	0.73 $\pm$ .06	11.48 $\pm$ 0.63	0.24 $\pm$ .04	0.76 $\pm$ .05
DPS	14.88 $\pm$ 1.21	0.52 $\pm$ .06	0.50 $\pm$ .07	13.81 $\pm$ 0.78	0.50 $\pm$ .06	0.56 $\pm$ .05
DAPS	14.84 $\pm$ 1.61	0.43 $\pm$ .06	0.59 $\pm$ .06	12.02 $\pm$ 0.82	0.31 $\pm$ .06	0.61 $\pm$ .06
QCS-SGM	18.11 $\pm$ 2.43	0.52 $\pm$ .10	0.52 $\pm$ .07	17.12 $\pm$ 1.84	0.49 $\pm$ .09	0.59 $\pm$ .06
SIM-DMIS	18.73 $\pm$ 1.94	0.52 $\pm$ .08	0.50 $\pm$ .07	17.36 $\pm$ 1.34	0.48 $\pm$ .08	0.55 $\pm$ .08

Table 1 : Quantitative results for one-bit recovery on the FFHQ dataset under different compression ratios

n/m

with additive Gaussian noise

\sigma=0.5

. Best results are shown in bold .

Figure 1 : Qualitative results on FFHQ dataset with $\sigma=0.5$ and $n/m=16$ .

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Methods	$n/m=16$			$n/m=32$
Methods	PSNR $\uparrow$	SSIM $\uparrow$	LPIPS $\downarrow$	PSNR $\uparrow$	SSIM $\uparrow$	LPIPS $\downarrow$
DiffPIR	11.50 $\pm$ 1.13	0.24 $\pm$ .05	0.78 $\pm$ .06	11.20 $\pm$ 0.94	0.18 $\pm$ .05	0.80 $\pm$ .06
DPS	14.53 $\pm$ 1.23	0.51 $\pm$ .06	0.52 $\pm$ .07	13.68 $\pm$ 0.78	0.49 $\pm$ .06	0.57 $\pm$ .05
DAPS	14.50 $\pm$ 1.48	0.40 $\pm$ .05	0.61 $\pm$ .07	13.57 $\pm$ 0.98	0.48 $\pm$ .06	0.56 $\pm$ .07
QCS-SGM	18.43 $\pm$ 2.47	0.52 $\pm$ .10	0.54 $\pm$ .07	17.00 $\pm$ 1.76	0.49 $\pm$ .09	0.61 $\pm$ .06
SIM-DMIS	18.32 $\pm$ 1.79	0.51 $\pm$ .08	0.53 $\pm$ .06	16.89 $\pm$ 1.17	0.47 $\pm$ .08	0.59 $\pm$ .08

Appendix

Table 2 : Quantitative results of one bit recovery on FFHQ dataset with different

m

and the additive Gaussian noise of

\sigma=1.0

. The best results are bold .

Methods	$n/m=16$			$n/m=32$
Methods	PSNR $\uparrow$	SSIM $\uparrow$	LPIPS $\downarrow$	PSNR $\uparrow$	SSIM $\uparrow$	LPIPS $\downarrow$
DiffPIR	10.73 $\pm$ 0.69	0.09 $\pm$ .03	0.77 $\pm$ .07	9.80 $\pm$ 0.54	0.06 $\pm$ .02	0.80 $\pm$ .07
DPS	14.38 $\pm$ 1.36	0.38 $\pm$ .05	0.69 $\pm$ .08	13.14 $\pm$ 0.76	0.35 $\pm$ .04	0.76 $\pm$ .08
DAPS	14.17 $\pm$ 1.51	0.24 $\pm$ .04	0.67 $\pm$ .07	12.27 $\pm$ 0.77	0.33 $\pm$ .05	0.78 $\pm$ .08
QCS-SGM	16.28 $\pm$ 1.92	0.39 $\pm$ .08	0.66 $\pm$ .08	14.13 $\pm$ 1.64	0.37 $\pm$ .08	0.72 $\pm$ .09
SIM-DMIS	17.03 $\pm$ 1.23	0.41 $\pm$ .06	0.60 $\pm$ .07	15.42 $\pm$ 0.98	0.40 $\pm$ .06	0.68 $\pm$ .08

Appendix

Table 3 : Quantitative results of one bit recovery on ImageNet dataset with different

m

and the additive Gaussian noise of

\sigma=0.5

. The best results are bold .

Figure 2 : Qualitative comparison of different methods on the FFHQ dataset with compression ratio $n/m=16$ and additive Gaussian noise $\sigma=0.5$ .

Figure 3 : Qualitative comparison between Diff-OneBit and PnP-OneBit on the ImageNet dataset with compression ratio $n/m=16$ under different noise levels ( $\sigma=0.5$ and $\sigma=1.0$ ).

Explore similar work

Breaking the Weak Recovery Limit in Random Phase Retrieval with Learned Regularizers
Sep 18, 2025Stanislas Ducotterd, Zhiyuan Hu, Michael Unser +1Image Inverse Problems
Biomedical Imaging Group, ´Ecole Polytechnique F´ed´erale de Lausanne
Tunable Latent Generative Priors for Compressed Sensing and Inverse Problems
Date pendingSean Gunn, Jorio Cocola, Oliver De Candido +2Generative Modeling Compressed Sensing
Northeastern University · Harvard University · Technical University of Munich +1
The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements
Sep 1, 2025Youssef Chaabouni, David GamarnikSparse Recovery Sample Complexity
Massachusetts Institute of Technology

Sep 18, 2025, eess.IVJ/K move · Enter open · S save

Breaking the Weak Recovery Limit in Random Phase Retrieval with Learned Regularizers

Stanislas Ducotterd, Zhiyuan Hu, Michael Unser, Jonathan Dong

Biomedical Imaging Group, ´Ecole Polytechnique F´ed´erale de Lausanne

Image Inverse Problems

Open paper AskPDF arXiv

We seek to recover an unknown signal from nonlinear amplitude-only measurements, a challenging inverse problem. Strong theoretical guarantees have been established for idealized random measurements, defining the sampling ratio required for signal recovery. However, these results neglect signal priors, which can fundamentally shift these limits, potentially enabling reconstruction with far fewer measurements and simpler models. We evaluate a variety of image priors in the context of severe undersampling with physically-grounded random measurement models. Our results show that these priors enable accurate recovery well below the weak recovery limit, the theoretical threshold required for recovery better than a random guess.

Abstract

Explore similar work

Breaking the Weak Recovery Limit in Random Phase Retrieval with Learned Regularizers

Tunable Latent Generative Priors for Compressed Sensing and Inverse Problems

The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements