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

Sep 18, 2025eess.IV

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

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.

Stanislas Ducotterd, Zhiyuan Hu, Michael Unser +1

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

Image Inverse Problems

Ask PDF

Date pendingcs.LG

Tunable Latent Generative Priors for Compressed Sensing and Inverse Problems

Latent generative models have emerged as powerful priors for solving inverse problems. These models typically represent a class of natural signals at a single, fixed complexity, governed by the latent dimensionality. This can be limiting: depending on the problem, a latent dimensionality that is too small may result in high representation error, while one that is too large may overfit to noise. We develop tunable latent priors for diffusion models, normalizing flows, and variational autoencoders, leveraging nested dropout. Across tasks including compressed sensing, inpainting, denoising, and phase retrieval, we show empirically that tunable priors consistently achieve lower reconstruction errors than fixed-complexity baselines. In the linear denoising setting, we derive the optimal complexity in closed form, showing how it depends on the noise level and the signal spectrum. This work demonstrates the potential of tunable latent generative priors and motivates both the development of supporting theory and their application across a wide range of inverse problems.

Sean Gunn, Jorio Cocola, Oliver De Candido +2

Northeastern University · Harvard University · Technical University of Munich +1

Generative Modeling Compressed Sensing Inverse Problems Diffusion Models

Ask PDF

Sep 1, 2025stat.ML

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

We consider the problem of support recovery for sparse binary signals from noisy linear measurements. For sparse Gaussian measurement matrices we identify sufficient conditions on the minimal sample size for maximum-likelihood recovery in the high-SNR regime

ds/p \to \infty

, where

p

denotes the signal dimension,

s

the number of non-zero components of the signal, and

d

the expected number of non-zero components per row of measurement. Combined with known lower bounds, this yields an information-theoretic threshold of order

s\log(p/s) / \log(ds/p)

, making explicit the price of measurement sparsity. In particular, we highlight a regime where the sample-complexity loss from measurement sparsity is logarithmic while the computational gain is nearly linear. Second, we study recovery after sparsifying an originally dense Gaussian design: the observations are generated from the dense design, while estimation uses an independently sparsified design and a rescaled response. In the proportional regime

s=αp

d=ψp

, we prove that, for every fixed target error level

δ

and every slack

\varepsilon>0

, a sample size of order

p/ψ^2

is sufficient for support recovery for arbitrarily small

ψ

Youssef Chaabouni, David Gamarnik

Massachusetts Institute of Technology

Sparse Recovery Sample Complexity

Ask PDF