What Can Be Recovered Under Sparse Adversarial Corruption? Assumption-Free Theory for Linear Measurements
This addresses a fundamental limitation in robust linear recovery for arbitrary matrices and vectors, offering an assumption-free theoretical framework that is foundational for signal processing and machine learning.
The paper tackles the problem of recovering an unknown vector from linear measurements corrupted by sparse adversarial errors, showing that the best recoverable set is x* + ker(U), where U is derived from rowspace intersections of submatrices of A, and provides a constructive method via ℓ0-norm minimization to achieve this.
Let $A \in \mathbb{R}^{m \times n}$ be an arbitrary, known matrix and $e$ a $q$-sparse adversarial vector. Given $y = A x^\star + e$ and $q$, we seek the smallest set containing $x^\star$ -- hence the one conveying maximal information about $x^\star$ -- that is uniformly recoverable from $y$ without knowing $e$. While exact recovery of $x^\star$ via strong (and often impractical) structural assumptions on $A$ or $x^\star$ (e.g., restricted isometry, sparsity) is well studied, recoverability for arbitrary $A$ and $x^\star$ remains open. Our main result shows that the best that one can hope to recover is $x^\star + \ker(U)$, where $U$ is the unique projection matrix onto the intersection of rowspaces of all possible submatrices of $A$ obtained by deleting $2q$ rows. Moreover, we prove that every $x$ that minimizes the $\ell_0$-norm of $y - A x$ lies in $x^\star + \ker(U)$, which then gives a constructive approach to recover this set.