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 polynomial time algorithm was known to achieve more than two.

本文提供了一个简单有效的算法来解决稀疏鲁棒线性回归问题，即从被稀疏噪声干扰的线性测量中估计一个稀疏的向量，对于高斯测量，基于L1回归的简单算法可以成功地估计任何小于0.239的锁定率，而该算法所需的测量数为O(klog(n/k))个，能够同时估计稀疏和稠密的w*，容忍大常数分数的离群值和对抗性而非分配性（例如，高斯）稠密噪声。

利用 L1 回归进行对抗稀疏噪声的压缩感知