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

arXiv:2510.24215v4 Announce Type: replace-cross Abstract: 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 leftlVert e rightrVert_0 leq 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 R^{m imes 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 leftlVert y - A x rightrVert_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.

Source: arXiv cs.LG | 2026-05-07