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

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 \leq 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\in\mathbb{R}^{m\times 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.