Robust Compressed Sensing using Generative Models

arXiv2006.09461MaRDI QIDQ6343071

Liu Liu, Ajil Jalal, Alexandros G. Dimakis, Constantine Caramanis

Publication date: 16 June 2020

Abstract: The goal of compressed sensing is to estimate a high dimensional vector from an underdetermined system of noisy linear equations. In analogy to classical compressed sensing, here we assume a generative model as a prior, that is, we assume the vector is represented by a deep generative model $G:mathbb{R}^{k}ightarrowmathbb{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.

Has companion code repository: https://github.com/ajiljalal/csgm-robust-neurips

This page was built for publication: Robust Compressed Sensing using Generative Models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6343071)