Abstract:

The decoding step in Compressed Sensing may be thought of as a maximum a posteriori (MAP) estimate where sparsity of the data is enforced through a highly structured prior. Since the full posterior encodes uncertainty about this estimate, a good prior should result in a posterior that is sufficiently concentrated around the MAP estimate if the data is representative of a sample from the prior.

By leveraging the properties of the Dantzig estimator and the principles behind Schwartz's theorem, we exhibit a universal finite-sample posterior concentration bound, which is the first theoretical evidence of this concentration phenomenon. Due to the imprecision of the estimates associated with Schwartz's theorem, this bound is suboptimal, but we may still utilize it to exhibit reasonable posterior concentration for some common priors. In certain cases, we demonstrate that a much stronger bound can be acquired through brute force.

In this talk, we shall discuss these results in depth and we shall also discuss ongoing work on sharpening these results.