Posterior sampling enables accurate recovery from one-bit noisy data
Recovery Guarantees for Posterior Sampling of One-Bit Compressed Sensing
Machine LearningInformation Theory
Summary
One-bit compressed sensing is a way to capture signals using very limited data, just a single bit per measurement, but noise can make it hard to recover the original signal. The authors study how many noisy one-bit measurements are needed to accurately reconstruct signals, assuming prior knowledge about signal types. They show that a method called posterior sampling can reliably recover signals when the number of measurements scales with certain complexity measures of the prior. Their approach remains effective even if the prior is only an approximation, and they demonstrate practical use with an algorithm tested on popular image datasets.
What this means in practice
- •For signal processing engineers: Design systems that reconstruct signals from extremely compressed and noisy measurements using prior-based posterior sampling methods.
- •For computer vision developers: Improve image reconstruction algorithms from limited and noisy binary measurements with diffusion prior-based posterior sampling.
Authors
Jing Ma, Yujia Wu, Zhaoqiang Liu
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.