Compressed Sensing with Adversarial Sparse Noise via L1 Regression
Compressed Sensing with Adversarial Sparse Noise via L1 Regression
复制标题
DOI：
10.4230/oasics.sosa.2019.19
复制
发表时间：
2018-09
期刊：
影响因子：
--
通讯作者：
Sushrut Karmalkar;Eric Price
中科院分区：
文献类型：
--
作者：
Sushrut Karmalkar;Eric Price
我们为\ emph {稀疏鲁棒线性回归}的问题提供了一种简单有效的算法。在这个问题中，人们想估计一个稀疏的向量$ w^* \ in \ mathbb {r}^n $从稀疏噪声损坏的线性测量中，可以任意更改对抗性选择的$ \ eta $ y的测量响应$ y的分数$ y $，并向响应引入有限的标准噪声。对于高斯测量值，我们表明，基于L1回归的简单算法可以成功估计任何$ \ eta <\ eta_0 \ of 0.239 $的$ W^*$，并且对于算法而言，此阈值很紧。该算法所需的测量数为$ O（k \ log \ frac {n} {k}）$对于$ k $ -sparse估计，它在所需数量的恒定因素范围内，而没有任何稀疏的噪声。在我们显示的三个属性中 - - 估计稀疏和密集的能力，$ w^*$;大量恒定分数的离群值的容忍度；宽容对抗性而不是分布（例如高斯）密集的噪声 - 据我们所知，以前的结果没有超过两个。
We present a simple and effective algorithm for the problem of \emph{sparse robust linear regression}. In this problem, one would like to estimate a sparse vector $w^* \in \mathbb{R}^n$ from linear measurements corrupted by sparse noise that can arbitrarily change an adversarially chosen $\eta$ fraction of measured responses $y$, as well as introduce bounded norm noise to the responses. For Gaussian measurements, we show that a simple algorithm based on L1 regression can successfully estimate $w^*$ for any $\eta < \eta_0 \approx 0.239$, and that this threshold is tight for the algorithm. The number of measurements required by the algorithm is $O(k \log \frac{n}{k})$ for $k$-sparse estimation, which is within constant factors of the number needed without any sparse noise. Of the three properties we show---the ability to estimate sparse, as well as dense, $w^*$; the tolerance of a large constant fraction of outliers; and tolerance of adversarial rather than distributional (e.g., Gaussian) dense noise---to the best of our knowledge, no previous result achieved more than two.