# Robustness to Sparse Adversarial Corruption in Arbitrary Linear Measurements: Beyond Exact Recovery

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 30 references that are in the map.
- First posted on arXiv 28 Oct 2025.

## Builds on (most cited first, 3 of 3)

- [Robust Regression via Hard Thresholding](https://mlsanity.com/paper/1506.02428/) (2015)
- [On Redundant Observability: From Security Index to Attack Detection and Resilient State Estimation](https://mlsanity.com/paper/1805.02640/) (2018)
- [Secure State Estimation with Byzantine Sensors: A Probabilistic Approach](https://mlsanity.com/paper/1903.05698/) (2019)

## Abstract (arXiv)

Recovery from linear measurements under sparse adversarial corruption is typically formulated as an exact-recovery problem: one seeks structural conditions on A (e.g., restricted isometry property) guaranteeing unique recovery of x^star from y = Ax^star + e with |e|0 ≤ q. However, these guarantees provide no guidance once exact recovery fails. This limitation obscures simple robustness phenomena -- for instance, repeated rows in A can preserve nontrivial information about x^star under sparse corruption. In this paper, we study what information about x^star can be uniformly recovered from y = Ax^star + e for arbitrary A∈ℝm× n and any q-sparse e. We show that the robust information is precisely x^star + ker(U), where U is the orthogonal projection onto the intersection of rowspaces of all submatrices of A obtained by deleting 2q rows. This clarifies how the row structure of A governs whether a q-sparse corruption allows exact, partial, or only trivial recovery. We further prove every x minimizing |y - A x|0 belongs to x^star + ker(U), yielding a constructive approach to recover this set. For i.i.d. Gaussian matrices, we establish a sharp phase transition between exact and trivial recovery. We sketch two applications: robust network tomography and signal reconstruction from oversampled DCT.