Timezone: »

Robust compressed sensing using generative models
Ajil Jalal · Liu Liu · Alexandros Dimakis · Constantine Caramanis

Mon Dec 07 09:00 PM -- 11:00 PM (PST) @ Poster Session 0 #68
We consider estimating a high dimensional signal in $\R^n$ using a sublinear number of linear measurements. In analogy to classical compressed sensing, here we assume a generative model as a prior, that is, we assume the signal is represented by a deep generative model $G: \R^k \rightarrow \R^n$. Classical recovery approaches such as empirical risk minimization (ERM) are guaranteed to succeed when the measurement matrix is sub-Gaussian. However, when the measurement matrix and measurements are heavy tailed or have outliers, recovery may fail dramatically. In this paper we propose an algorithm inspired by the Median-of-Means (MOM). Our algorithm guarantees recovery for heavy tailed data, even in the presence of outliers. Theoretically, our results show our novel MOM-based algorithm enjoys the same sample complexity guarantees as ERM under sub-Gaussian assumptions. Our experiments validate both aspects of our claims: other algorithms are indeed fragile and fail under heavy tailed and/or corrupted data, while our approach exhibits the predicted robustness.

Author Information

Ajil Jalal (University of Texas at Austin)
Liu Liu (University of Texas at Austin)
Alex Dimakis (University of Texas, Austin)
Constantine Caramanis (UT Austin)

More from the Same Authors