Research map / Learning theory and algorithms / Sample complexity

Recovery Guarantees for Posterior Sampling of One-Bit Compressed Sensing

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: Sample complexity of learning distributions

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Extends distributional posterior-sampling theory from linear to noisy one-bit compressed sensing on the sphere, giving covering-number upper and lower sample-complexity bounds and a diffusion-based plug-and-play sampler (PnP-OneBit) evaluated on FFHQ and ImageNet.

Problem

Sample complexity of reliable recovery of unit-norm signals drawn from an arbitrary prior from noisy one-bit (sign) Gaussian measurements, and how it is governed by the prior's approximate covering number, including robustness under learned prior mismatch.

Approach

Characterizes one-bit posterior sampling sample complexity via the (eta,delta)-approximate covering number of the prior on the sphere, using a near-far test on expected Hamming distances (with a noise-dependent separation gap) plus union bound over covering caps; handles prior mismatch via Renyi stability under Wasserstein-infinity coupling; and matches the leading log-covering term with an inform

Key results

• On FFHQ at n/m=16 with sigma=0.5, PnP-OneBit reaches 22.96 PSNR, 0.69 SSIM, 0.33 LPIPS, versus 21.95 PSNR for Diff-OneBit (the strongest baseline).
• At n/m=32 on FFHQ, PnP-OneBit reports 19.64 PSNR and 0.58 SSIM versus 18.68 PSNR for Diff-OneBit.
• The upper bound m = O((log Cov + log(1/zeta)) eta^-2) for small noise and the lower bound m >= c(log Cov_{3eta,4delta}(R) + log(6delta) - 25) match in the leading log-covering term.

Limitations

• Upper bound has an extra Delta_sigma^{-2} factor not matched by the lower bound.
• Analysis assumes i.i.d. Gaussian sensing and additive Gaussian noise before quantization; adversarial noise is left open.
• Lower bound does not cover general randomized or adaptive sensing strategies.

Experimental setup

Datasets: FFHQ ImageNet

Benchmarks: FFHQ ImageNet

Metrics: PSNR SSIM LPIPS

Baselines: DiffPIR DPS DAPS QCS-SGM SIM-DMIS Diff-OneBit

Builds on: posterior sampling for linear compressed sensing with arbitrary data priors Diff-OneBit PnP-DM split Gibbs sampler binary stable embeddings

Closest papers by meaning

• Instance-Optimal Compressed Sensing via Posterior Sampling (ICML 2021 · similarity 0.94)
• How many measurements are enough? Bayesian recovery in inverse problems with general distributions (NeurIPS 2025 · similarity 0.88)
• The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements (NeurIPS 2025 · similarity 0.86)
• Diffusion Posterior Sampling is Computationally Intractable (ICML 2024 · similarity 0.86)
• Provably Robust Score-Based Diffusion Posterior Sampling for Plug-and-Play Image Reconstruction (NeurIPS 2024 · similarity 0.85)
• Sparse Bayesian Generative Modeling for Compressive Sensing (NeurIPS 2024 · similarity 0.85)