# Robust High Dimensional Sparse Regression and Matching Pursuit

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jan 2013.

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

- [Poisoning Attacks and Defenses on Artificial Intelligence: A Survey](https://mlsanity.com/paper/2202.10276/) (2022)
- [Reducing Certified Regression to Certified Classification for General Poisoning Attacks](https://mlsanity.com/paper/2208.13904/) (2022)
- [UTrace: Poisoning Forensics for Private Collaborative Learning](https://mlsanity.com/paper/2409.15126/) (2024)
- [Robustifying Algorithms of Learning Latent Trees with Vector Variables](https://mlsanity.com/paper/2106.00885/) (2021)
- [New data poison attacks on machine learning classifiers for mobile exfiltration](https://mlsanity.com/paper/2210.11592/) (2022)

## Abstract (arXiv)

We consider high dimensional sparse regression, and develop strategies able to deal with arbitrary -- possibly, severe or coordinated -- errors in the covariance matrix X. These may come from corrupted data, persistent experimental errors, or malicious respondents in surveys/recommender systems, etc. Such non-stochastic error-in-variables problems are notoriously difficult to treat, and as we demonstrate, the problem is particularly pronounced in high-dimensional settings where the primary goal is em support recovery of the sparse regressor. We develop algorithms for support recovery in sparse regression, when some number n1 out of n+n1 total covariate/response pairs are it arbitrarily (possibly maliciously) corrupted. We are interested in understanding how many outliers, n1, we can tolerate, while identifying the correct support. To the best of our knowledge, neither standard outlier rejection techniques, nor recently developed robust regression algorithms (that focus only on corrupted response variables), nor recent algorithms for dealing with stochastic noise or erasures, can provide guarantees on support recovery. Perhaps surprisingly, we also show that the natural brute force algorithm that searches over all subsets of n covariate/response pairs, and all subsets of possible support coordinates in order to minimize regression error, is remarkably poor, unable to correctly identify the support with even n1 = O(n/k) corrupted points, where k is the sparsity. This is true even in the basic setting we consider, where all authentic measurements and noise are independent and sub-Gaussian. In this setting, we provide a simple algorithm -- no more computationally taxing than OMP -- that gives stronger performance guarantees, recovering the support with up to n1 = O(n/(√k log p)) corrupted points, where p is the dimension of the signal to be recovered.