# Compressed Sensing with Adversarial Sparse Noise via L1 Regression

arXiv: https://arxiv.org/abs/1809.08055 · HTML: https://mlsanity.com/paper/1809.08055/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Sep 2018.

## Built on by (most cited first, 7 of 7)

- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Estimation Contracts for Outlier-Robust Geometric Perception](https://mlsanity.com/paper/2208.10521/) (2022)
- [Efficient List-Decodable Regression using Batches](https://mlsanity.com/paper/2211.12743/) (2022)
- [Linear Regression using Heterogeneous Data Batches](https://mlsanity.com/paper/2309.01973/) (2023)
- [Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions](https://mlsanity.com/paper/2309.11657/) (2023)
- [A Bayesian Robust Regression Method for Corrupted Data Reconstruction](https://mlsanity.com/paper/2212.12787/) (2022)
- [Lasso and Partially-Rotated Designs](https://mlsanity.com/paper/2505.11093/) (2025)

## Abstract (arXiv)

We present a simple and effective algorithm for the problem of sparse robust linear regression. In this problem, one would like to estimate a sparse vector w^* ∈ ℝn from linear measurements corrupted by sparse noise that can arbitrarily change an adversarially chosen η 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 η < η0 ≈ 0.239, and that this threshold is tight for the algorithm. The number of measurements required by the algorithm is O(k log fracnk) 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.