Timezone: »

 
Spotlight
Instance-Optimal Compressed Sensing via Posterior Sampling
Ajil Jalal · Sushrut Karmalkar · Alexandros Dimakis · Eric Price

Wed Jul 21 07:20 AM -- 07:25 AM (PDT) @
in Sparsity and Compressed Sensing »

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.

Keywords: Sparsity and Compressed Sensing · Algorithms

Author Information

Ajil Jalal (University of Texas at Austin)
Sushrut Karmalkar (University of Texas at Austin)
Alexandros Dimakis (UT Austin)

Alex Dimakis is an Associate Professor at the Electrical and Computer Engineering department, University of Texas at Austin. He received his Ph.D. in electrical engineering and computer sciences from UC Berkeley. He received an ARO young investigator award in 2014, the NSF Career award in 2011, a Google faculty research award in 2012 and the Eli Jury dissertation award in 2008. He is the co-recipient of several best paper awards including the joint Information Theory and Communications Society Best Paper Award in 2012. His research interests include information theory, coding theory and machine learning.

Eric Price (UT-Austin)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors