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 ≤ 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.