Recovery Guarantees for Posterior Sampling of One-Bit Compressed Sensing
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.
Related
- Superfast Spectral Compressed Sensing with Quadratic Convergence
- Phase Transition in Binary Compressed Sensing via Annealing with Adaptive Regularization
- Compressed Sensing with Quantized Tensor Trains (QTTs)
- Learned Score-Based Turbo Message Passing for Channel Recovery From Spatially Compressed Measurements
- Lifted Restricted Isometry Property and Fast Algorithm for Spectral Compressed Sensing With Near-Optimal Sample Complexity
BibTeX
@misc{ma2026recovery,
title = {{Recovery Guarantees for Posterior Sampling of One-Bit Compressed Sensing}},
author = {Jing Ma and Yujia Wu and Zhaoqiang Liu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.11834},
eprint = {2610.11834},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.11834},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Recovery Guarantees for Posterior Sampling of One-Bit Compressed Sensing
AU - Jing Ma
AU - Yujia Wu
AU - Zhaoqiang Liu
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.11834
UR - https://arxiv.org/abs/2610.11834
AB - 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.
ER -