Robust compressed sensing using generative models
Robust compressed sensing using generative models
复制标题
DOI：
--
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
A. Jalal;Liu Liu-Liu;A. Dimakis;C. Caramanis
中科院分区：
文献类型：
--
作者：
A. Jalal;Liu Liu-Liu;A. Dimakis;C. Caramanis
压缩感知的目标是从欠确定的噪声线性方程组中估计高维向量。类似于经典的压缩感知，这里我们假设一个生成模型作为先验，也就是说，我们假设向量由一个深度生成模型$G：\mathbb{R}^k\mathbb{R}^n$表示。当测量矩阵为亚高斯时，经典的恢复方法，如经验风险最小化(ERM)，保证是成功的。然而，当测量矩阵和测量值是重尾或有异常值时，恢复可能会显著失败。在本文中，我们提出了一种受均值中值(MoM)启发的算法。我们的算法保证了对重尾数据的恢复，即使在存在离群点的情况下也是如此。理论上，我们的结果表明，在亚高斯假设下，基于矩量法的新算法具有与ERM相同的样本复杂度保证。我们的实验验证了我们声明的这两个方面：其他算法确实很脆弱，在重尾和/或损坏的数据下失败，而我们的方法表现出预期的健壮性。
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 \rightarrow \mathbb{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.