Timezone: »
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.
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)
-
2021 Spotlight: Instance-Optimal Compressed Sensing via Posterior Sampling »
Wed. Jul 21st 02:20 -- 02:25 PM Room
More from the Same Authors
-
2023 Poster: High-dimensional Location Estimation via Norm Concentration for Subgamma Vectors »
Shivam Gupta · Jasper Lee · Eric Price -
2023 Poster: Restoration-Degradation Beyond Linear Diffusions: A Non-Asymptotic Analysis For DDIM-type Samplers »
Sitan Chen · Giannis Daras · Alexandros Dimakis -
2022 Poster: Hardness and Algorithms for Robust and Sparse Optimization »
Eric Price · Sandeep Silwal · Samson Zhou -
2022 Spotlight: Hardness and Algorithms for Robust and Sparse Optimization »
Eric Price · Sandeep Silwal · Samson Zhou -
2022 Poster: Score-Guided Intermediate Level Optimization: Fast Langevin Mixing for Inverse Problems »
Giannis Daras · Yuval Dagan · Alexandros Dimakis · Constantinos Daskalakis -
2022 Spotlight: Score-Guided Intermediate Level Optimization: Fast Langevin Mixing for Inverse Problems »
Giannis Daras · Yuval Dagan · Alexandros Dimakis · Constantinos Daskalakis -
2022 Poster: Linear Bandit Algorithms with Sublinear Time Complexity »
Shuo Yang · Tongzheng Ren · Sanjay Shakkottai · Eric Price · Inderjit Dhillon · Sujay Sanghavi -
2022 Spotlight: Linear Bandit Algorithms with Sublinear Time Complexity »
Shuo Yang · Tongzheng Ren · Sanjay Shakkottai · Eric Price · Inderjit Dhillon · Sujay Sanghavi -
2021 : Invited Talk: Alex Dimakis »
Alexandros Dimakis -
2021 Poster: Provable Lipschitz Certification for Generative Models »
Matt Jordan · Alexandros Dimakis -
2021 Spotlight: Provable Lipschitz Certification for Generative Models »
Matt Jordan · Alexandros Dimakis -
2021 Poster: Fairness for Image Generation with Uncertain Sensitive Attributes »
Ajil Jalal · Sushrut Karmalkar · Jessica Hoffmann · Alexandros Dimakis · Eric Price -
2021 Spotlight: Fairness for Image Generation with Uncertain Sensitive Attributes »
Ajil Jalal · Sushrut Karmalkar · Jessica Hoffmann · Alexandros Dimakis · Eric Price -
2021 Poster: Solving Inverse Problems with a Flow-based Noise Model »
Jay Whang · Qi Lei · Alexandros Dimakis -
2021 Spotlight: Solving Inverse Problems with a Flow-based Noise Model »
Jay Whang · Qi Lei · Alexandros Dimakis -
2021 Poster: Intermediate Layer Optimization for Inverse Problems using Deep Generative Models »
Giannis Daras · Joseph Dean · Ajil Jalal · Alexandros Dimakis -
2021 Poster: Composing Normalizing Flows for Inverse Problems »
Jay Whang · Erik Lindgren · Alexandros Dimakis -
2021 Spotlight: Intermediate Layer Optimization for Inverse Problems using Deep Generative Models »
Giannis Daras · Joseph Dean · Ajil Jalal · Alexandros Dimakis -
2021 Spotlight: Composing Normalizing Flows for Inverse Problems »
Jay Whang · Erik Lindgren · Alexandros Dimakis -
2020 Poster: On the Power of Compressed Sensing with Generative Models »
Akshay Kamath · Eric Price · Sushrut Karmalkar -
2020 Poster: SGD Learns One-Layer Networks in WGANs »
Qi Lei · Jason Lee · Alexandros Dimakis · Constantinos Daskalakis -
2020 Poster: Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent »
Surbhi Goel · Aravind Gollakota · Zhihan Jin · Sushrut Karmalkar · Adam Klivans -
2019 : Alex Dimakis: Coding Theory for Distributed Learning »
Alexandros Dimakis -
2019 Poster: Learning a Compressed Sensing Measurement Matrix via Gradient Unrolling »
Shanshan Wu · Alexandros Dimakis · Sujay Sanghavi · Felix Xinnan Yu · Daniel Holtmann-Rice · Dmitry Storcheus · Afshin Rostamizadeh · Sanjiv Kumar -
2019 Oral: Learning a Compressed Sensing Measurement Matrix via Gradient Unrolling »
Shanshan Wu · Alexandros Dimakis · Sujay Sanghavi · Felix Xinnan Yu · Daniel Holtmann-Rice · Dmitry Storcheus · Afshin Rostamizadeh · Sanjiv Kumar -
2019 Poster: Adversarial examples from computational constraints »
Sebastien Bubeck · Yin Tat Lee · Eric Price · Ilya Razenshteyn -
2019 Oral: Adversarial examples from computational constraints »
Sebastien Bubeck · Yin Tat Lee · Eric Price · Ilya Razenshteyn -
2018 Poster: Gradient Coding from Cyclic MDS Codes and Expander Graphs »
Netanel Raviv · Rashish Tandon · Alexandros Dimakis · Itzhak Tamo -
2018 Oral: Gradient Coding from Cyclic MDS Codes and Expander Graphs »
Netanel Raviv · Rashish Tandon · Alexandros Dimakis · Itzhak Tamo -
2017 Poster: Identifying Best Interventions through Online Importance Sampling »
Rajat Sen · Karthikeyan Shanmugam · Alexandros Dimakis · Sanjay Shakkottai -
2017 Poster: Cost-Optimal Learning of Causal Graphs »
Murat Kocaoglu · Alexandros Dimakis · Sriram Vishwanath -
2017 Poster: On Approximation Guarantees for Greedy Low Rank Optimization »
RAJIV KHANNA · Ethan R. Elenberg · Alexandros Dimakis · Joydeep Ghosh · Sahand Negahban -
2017 Talk: Identifying Best Interventions through Online Importance Sampling »
Rajat Sen · Karthikeyan Shanmugam · Alexandros Dimakis · Sanjay Shakkottai -
2017 Talk: On Approximation Guarantees for Greedy Low Rank Optimization »
RAJIV KHANNA · Ethan R. Elenberg · Alexandros Dimakis · Joydeep Ghosh · Sahand Negahban -
2017 Talk: Cost-Optimal Learning of Causal Graphs »
Murat Kocaoglu · Alexandros Dimakis · Sriram Vishwanath -
2017 Poster: Exact MAP Inference by Avoiding Fractional Vertices »
Erik Lindgren · Alexandros Dimakis · Adam Klivans -
2017 Poster: Compressed Sensing using Generative Models »
Ashish Bora · Ajil Jalal · Eric Price · Alexandros Dimakis -
2017 Poster: Gradient Coding: Avoiding Stragglers in Distributed Learning »
Rashish Tandon · Qi Lei · Alexandros Dimakis · Nikos Karampatziakis -
2017 Talk: Gradient Coding: Avoiding Stragglers in Distributed Learning »
Rashish Tandon · Qi Lei · Alexandros Dimakis · Nikos Karampatziakis -
2017 Talk: Compressed Sensing using Generative Models »
Ashish Bora · Ajil Jalal · Eric Price · Alexandros Dimakis -
2017 Talk: Exact MAP Inference by Avoiding Fractional Vertices »
Erik Lindgren · Alexandros Dimakis · Adam Klivans