Recovery Guarantees for Posterior Sampling of One-Bit Compressed Sensing

1 Introduction

• The paper asks how noisy one-bit recovery for signals drawn from arbitrary sphere priors depends on the approximate covering number of high-probability regions.This distributional view accounts for where prior probability mass lies, unlike bounds based on the entire support.Source: §1 · pp. 1–2

1.1 Related works

• Prior one-bit guarantees largely concern structured classes or generator ranges, while this work analyzes arbitrary sphere distributions using approximate covering complexity.The analysis extends posterior sampling for linear Gaussian measurements, addressing binary separation, noise, and prior mismatch.Source: §1.1 · p. 2

1.2 Contributions

• The paper establishes a posterior-sampling upper bound robust to sufficiently close learned priors and a nearly matching lower bound for reliable recovery.The upper bound uses Wasserstein closeness; the lower bound shows the approximate covering number is unavoidable.Source: §1.2 · p. 3
• A diffusion-prior plug-and-play method approximates posterior sampling, and experiments evaluate its effectiveness for image recovery.The experiments use FFHQ and ImageNet.Source: §1.2 · p. 3

Signal and observation distances

• Signal discrepancy is measured by normalized geodesic distance on the unit sphere, while binary observations use normalized Hamming distance.The setup also identifies the Gaussian noise level σ and standard Gaussian cumulative distribution function Φ.Source: §2 · p. 3

Approximate covering number

• The (η, δ)-approximate covering number is introduced for a distribution on the sphere using geodesic η-caps.The supplied definition identifies the cap and distribution parameters.Source: §2 · p. 3

Geodesic Wasserstein distance

• Geodesic Wasserstein-p distance is defined for sphere distributions through their couplings, and the corresponding Wasserstein-∞ distance is also introduced.Source: §2 · p. 3

One-bit separation gap

• The one-bit separation gap ∆σ(s, u) is defined from fσ(su) − fσ(u) and is nonnegative when s > 1 by monotonicity.Source: §2 · p. 3

Other model quantities

• The preliminaries define the maximum row ℓ2 norm of A and introduce the one-bit probit conditional likelihood Pr(y|x, A).Source: §2 · p. 3

3.1 Upper bound

• With sufficiently small prior mismatch, m ≥ C[log Covη,δ(R)+log(2/ζ)]/Δσ(c,η̄)^2 gives recovery within (c+1)η̄+εδ, with conditional failure at most 2δ+ζ.The measurement matrix is i.i.d. Gaussian, and the stated probability over its draw is at least 1−ζ.Source: §3.1 · p. 4
• The upper bound pays a Δσ(c,η̄)^−2 factor because sign-only measurements distinguish separated signals through a gap in expected Hamming disagreements.The gap is Δσ(c,η̄)=fσ(cη̄)−fσ(η̄).Source: §3.1 · pp. 4–5

3.2 Lower bound

• Any estimator achieving O(η) recovery with constant success probability requires m ≳ log Cov3η,4δ(R), for deterministic or Gaussian sensing matrices.The lower-bound argument combines a one-bit channel information bound with a spherical Fano inequality.Source: §3.2 · pp. 6–7
• The upper and lower bounds nearly match in their leading prior-dependent term, but the lower-bound analysis does not establish a universal result for adaptive or more general randomized sensing.The stated lower bounds cover fixed deterministic matrices and i.i.d. Gaussian matrices; the deterministic result permits prior-aware matrix design when the matrix is independent of the realized signal.Source: §3.2 · p. 7

4.1 Plug-and-play approach for one-bit measurements

• Because exact high-dimensional posterior inference is intractable, PnP-OneBit uses diffusion models as a learned prior to approximate posterior sampling.The method aligns prior sampling with a diffusion posterior under a condition on the diffusion time and coupling parameter.Source: §4.1 · pp. 8–9
• PnP-OneBit uses split Gibbs sampling to alternate between one-bit likelihood sampling and diffusion-based prior sampling.The likelihood step uses Langevin Monte Carlo, and the prior step uses DDIM denoising.Source: §4.1 · pp. 8–9

4.2 Quantitative results

• Across FFHQ and ImageNet, PnP-OneBit consistently achieves strong reconstruction performance on all evaluated metrics, including at n/m = 32.The FFHQ quantitative results use σ = 0.5; the reported comparisons also include ImageNet evaluations.Source: §4.2 · pp. 9–10, Table 1 · p. 10
• At σ = 0.5 and n/m = 16 on FFHQ, the visual comparisons show PnP-OneBit mitigating high-frequency oversmoothing and retaining texture.The comparison passage contrasts its posterior sampling with point-estimate methods such as Diff-OneBit.Source: §4.2 · p. 10, Figure 1 · p. 10

5 Conclusion

• The paper establishes a posterior-sampling upper bound tied to the logarithm of the approximate covering number, a learned-prior mismatch guarantee, and a lower bound for reliable estimators.It concludes that reliable recovery can be characterized by the high-probability geometric complexity of the signal prior.Source: §5 · p. 10
• The theory is for additive Gaussian noise before quantization; whether similar robust posterior-sampling bounds hold for adversarial model noise remains open.Source: §5 · p. 10

A Upper bound proofs

• The upper-bound proof uses Gaussian rotational invariance to relate expected Hamming distance to geodesic distance, then builds an exponentially accurate one-bit near–far test.It applies the test over an approximate geodesic cover of a high-probability region and uses a union bound.Source: A Upper bound proofs · p. 15
• For learned-prior mismatch, the proof truncates the distributions into regular and residual components, controls the regular parts through W∞,geo closeness, and transfers the guarantee using Rényi stability.The residual components add a failure probability of 2δ.Source: A Upper bound proofs · p. 15

• The proof applies Sheppard’s formula to jointly zero-mean Gaussian pre-quantization variables to relate their correlation to sign observations.Source: §A.1 · p. 15
• It computes the variables’ correlation from their variances and covariance, using independence and zero mean of the measurement noise.Source: §A.1 · p. 15
• The resulting expression gives the normalized Hamming distance between the observation vectors.Source: §A.1 · p. 16

• Conditional on the signal, the measurement and noise pairs are i.i.d., making the one-bit observations independent, identically distributed Bernoulli variables.Source: §A.2 · p. 16
• The proof uses the nondecreasing property of fσ and Hoeffding’s inequality to bound the near-signal case uniformly over signals within η.Source: §A.2 · p. 16
• It also applies Hoeffding’s inequality to bound the far-signal case uniformly over signals at distance at least cη.Source: §A.2 · p. 16

A.3 Proof of Lemma 3.4

• The proof partitions overlapping spherical caps into disjoint blocks, reduces each block’s far-region error to binary near–far testing, and uses counting to replace N + 1 with N.The final count uses that a point in the covered region belongs to at most N − 1 far regions.Source: §A.3 · pp. 17, 20
• The A.3 bound controls the probability that a posterior sample lies at geodesic distance at least (c + 1)η from the true signal using the cover size and one-bit separation.The displayed probability bound is stated in the proof’s conclusion.Source: §A.3 · pp. 17, 20

A.4 Proof of Lemma 3.5

• For prior mismatch, a W∞ coupling places the auxiliary signal within ε of the true signal, shifting the tail event’s distance threshold by ε.An error at distance at least d + ε from the true signal implies distance at least d from the auxiliary signal.Source: §A.4 · p. 21
• A Rényi/Hölder change of measure converts posterior-sampling error under the true observation into error under the auxiliary observation.The proof controls the change-of-measure moment using the unquantized joint Gaussian observation laws and data processing.Source: §A.4 · pp. 21–22

A.5 Proof of Theorem 3.1

• The proof decomposes both priors into good components and residual components of weight 2δ, converting Wp closeness into a W∞ mismatch bound on the good parts.The residual components may be arbitrary distributions, but their weights in the original distributions are at most 2δ.Source: §A.5 · p. 24
• The good part of the learned prior is covered by at most Covη,δ(R) spherical caps, allowing the matched-prior bound to control recovery before transferring it to the full prior.The cover radius is η̄, which incorporates the effective mismatch level.Source: §A.5 · pp. 24–25
• With probability at least 1 − ζ over A, the recovery-error probability is at most 2δ + ζ at threshold (c + 1)η̄ + εδ.Here εδ = ρ/δ^(1/p) and η̄ = η + εδ.Source: §A.5 · pp. 24, 28

B.1 Proof of Lemma 3.7

• The information bound is proved separately for Gaussian and deterministic measurement matrices, using conditional independence of observations and a Gaussian probability calculation.For a fixed matrix, the observations are conditionally independent given the signal; the Gaussian case bounds conditional mutual information.Source: §B.1 · pp. 29, 31

B.2 Proof of Lemma 3.8

• For a continuous prior, signals and estimates are mapped to a finite spherical net, and prior probabilities are quantized with total probability loss at most δ.The chosen quantization preserves a recovery-probability lower bound of 1 − 2δ.Source: §B.2 · p. 32
• The discretized covering bound transfers to the continuous prior by relaxing the covering radius to 3η when the net resolution is γ = η/5.The covered prior mass is adjusted for the probability lost during discretization.Source: §B.2 · p. 32

B.3 Proof of Theorem 3.6

• The lower-bound proof isolates a residual component with mass greater than 10δ; any method succeeding with probability at least 1 − δ on the full prior must succeed with probability at least 0.9 on that component.It then applies a spherical Fano inequality and a one-bit information bound.Source: §B.3 · p. 33

C.1 Preliminary for diffusion

• The diffusion preliminary describes forward corruption of data by an SDE and reverse reconstruction using a trained noise predictor and an equivalent probability-flow ODE.The predictor estimates additive Gaussian noise, and the score is approximated from that predictor.Source: §C.1 · p. 34

C.2 Align between likelihood and prior

• The prior-sampling conditional is matched to the diffusion model’s posterior of clean data given noisy data by setting x = x0, ϱ = σt/αt, and z(k) = xt/αt.The pretrained diffusion model approximates the otherwise intractable reverse transition.Source: §C.2 · p. 35

C.3 Detailed algorithm

• PnP-OneBit combines the measurement-likelihood gradient with MCMC sampling from a likelihood-based conditional distribution.The section introduces the likelihood, its gradient, and the algorithmic workflow.Source: §C.3 · pp. 35–36

D.1 Implementation details

• The experiments use pretrained diffusion models from Dhariwal & Nichol [20] and Choi et al. [16], retaining their original noise schedules.FFHQ [38] and ImageNet [60] are used; the datasets and models are used under their stated licenses.Source: §D.1 · p. 36
• The coupling parameter follows ϱ_k = max{ν_kϱ_0, ϱ_min}, with ϱ_0 = 10, ν = 0.9, and ϱ_min = 0.3.The iterative process uses J = 100 MCMC steps, κ = 0.01 learning rate, T = 100 diffusion timesteps, η = 0.5 DDIM noise, and K = 100 outer iterations.Source: §D.1 · p. 36
• Baseline methods use their respective publications’ default parameters, and all experiments run on one Nvidia RTX 4090 (24GB).Source: §D.1 · p. 37

D.2 Quantitative results

• ImageNet results confirm that PnP-OneBit effectively recovers one-bit signals for diverse, complex natural scenes.Source: §D.2 · p. 37, Table 3 · p. 37
• Compared with Diff-OneBit, PnP-OneBit exhibits slightly larger standard deviation, while its posterior sampling preserves fine high-frequency details.The passage attributes the increased variance to stochastic transitions and says preserved details contribute to improved reconstruction quality.Source: §D.2 · p. 37
• At FFHQ σ = 1.0 and n/m = 16 or 32, PnP-OneBit consistently maintains the highest performance under increased noise corruption.Source: Table 2 · p. 37, §D.2 · p. 37
• On FFHQ at n/m = 16 and σ = 0.5, PnP-OneBit recovers facial details with fewer visual artifacts than evaluated baselines.Source: §D.2 · p. 37, Figure 2 · p. 38