{"ID":2848999,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.24215","arxiv_id":"2510.24215","title":"What Can Be Recovered Under Sparse Adversarial Corruption? Assumption-Free Theory for Linear Measurements","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 $\\left\\lVert e \\right\\rVert_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 \\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 $\\left\\lVert y - A x \\right\\rVert_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.","short_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 $\\left\\lVert e \\right\\rVert_0 \\leq q$. How...","url_abs":"https://arxiv.org/abs/2510.24215","url_pdf":"https://arxiv.org/pdf/2510.24215v4","authors":"[\"Vishal Halder\",\"Alexandre Reiffers-Masson\",\"Abdeldjalil Aïssa-El-Bey\",\"Gugan Thoppe\"]","published":"2025-10-28T09:29:46Z","proceeding":"cs.IT","tasks":"[\"cs.IT\",\"cs.LG\",\"eess.SP\"]","methods":"[]","has_code":false}