What Can Be Recovered Under Sparse Adversarial Corruption? Assumption-Free Theory for Linear Measurements

Recovery from linear measurements under sparse adversarial corruption is typically formulated as an exact-recovery problem: one seeks structural conditions on $A$ (e.g., the restricted isometry property) that guarantee unique recovery of $x^{\star }$ from $y=A{x}^{\star }+e$ with ${\parallel e\parallel }_0\le q$. However, in practice, these conditions are rarely met and are hard to verify, and so the existing guarantees provide no guidance once exact recovery fails. This limitation obscures even simple robustness phenomena – for instance, repeated rows in $A$ can preserve nontrivial information about $x^{\star }$ under sparse corruption. In this paper, we address the more general question: for arbitrary $A\in {\mathbb{R}}^{m\times n}$, what information about $x^{\star }$ remains robust in $y$ despite any $q$-sparse adversarial corruption $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 characterization clarifies, for each sparsity level $q$, how the row structure of $A$ determines whether a $q$-sparse $e$ allows exact, partial, or only trivial recovery, thereby extending the standard exact-recovery framework. We further prove that every $x$ that minimizes ${\parallel y-Ax\parallel }_0$ belongs to $x^{\star }+\ker (U)$, yielding a constructive approach to recover this set. For i.i.d. Gaussian $A$, we show a sharp phase transition: depending on $m$, $n$, and $q$, either exact recovery holds or no nontrivial recovery is possible. We sketch two applications: robust network tomography and signal reconstruction from oversampled DCT measurements.