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

ArXi:2510.24215v4 Announce Type: replace-cross 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.