Abstract:
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.
