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

Abstract

Recovery from linear measurements under sparse adversarial corruption is typically formulated as an exact-recovery problem: one seeks structural conditions on $\mathbf{A}$ (e.g., restricted isometry property) guaranteeing unique recovery of ${\mathbf{x}}^{\star }$ from $\mathbf{y}=\mathbf{A}{\mathbf{x}}^{\star }+\mathbf{e}$ with $\Vert \mathbf{e}{\Vert }_0\le q$. However, these guarantees provide no guidance once exact recovery fails. This limitation obscures simple robustness phenomena -- for instance, repeated rows in $\mathbf{A}$ can preserve nontrivial information about ${\mathbf{x}}^{\star }$ under sparse corruption. In this paper, we study what information about ${\mathbf{x}}^{\star }$ can be \emph{uniformly} recovered from $\mathbf{y}=\mathbf{A}{\mathbf{x}}^{\star }+\mathbf{e}$ for arbitrary $\mathbf{A}\in {\mathbb{R}}^{m\times n}$ and \emph{any} $q$-sparse $\mathbf{e}$. We show that the robust information is precisely ${\mathbf{x}}^{\star }+\ker (\mathbf{U})$, where $\mathbf{U}$ is the orthogonal projection onto the intersection of rowspaces of all submatrices of $\mathbf{A}$ obtained by deleting $2q$ rows. This clarifies how the row structure of $\mathbf{A}$ governs whether a $q$-sparse corruption allows exact, partial, or only trivial recovery. We further prove every $\mathbf{x}$ minimizing $\Vert \mathbf{y}-\mathbf{Ax}{\Vert }_0$ belongs to ${\mathbf{x}}^{\star }+\ker (\mathbf{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.

26 pages, 3 figures; preprint submitted a journal