Instance-Optimal Compressed Sensing via Posterior Sampling
This work addresses compressed sensing for signals from arbitrary priors, offering a robust and near-optimal solution, though it is incremental as it builds on existing posterior sampling methods.
The paper tackles the problem of compressed sensing with signals from known prior distributions, showing that the posterior sampling estimator achieves near-optimal recovery guarantees for Gaussian measurements and any prior, with robustness to model mismatch. Empirical results demonstrate accurate estimates with more diversity than MAP when implemented with deep generative priors using Langevin dynamics.
We characterize the measurement complexity of compressed sensing of signals drawn from a known prior distribution, even when the support of the prior is the entire space (rather than, say, sparse vectors). We show for Gaussian measurements and \emph{any} prior distribution on the signal, that the posterior sampling estimator achieves near-optimal recovery guarantees. Moreover, this result is robust to model mismatch, as long as the distribution estimate (e.g., from an invertible generative model) is close to the true distribution in Wasserstein distance. We implement the posterior sampling estimator for deep generative priors using Langevin dynamics, and empirically find that it produces accurate estimates with more diversity than MAP.