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

Let \(\bm{A} \in \mathbb{R}^{m \times n}\) be an arbitrary, known matrix and \(\bm{e}\) a \(q\)-sparse adversarial vector. Given \(\bm{y} = \bm{A} x^* + \bm{e}\) and \(q\), we seek the smallest set containing \(x^*\)-hence the one conveying maximal information about \(x^*\)-that is uniformly recoverable from \(\bm{y}\) without knowing \(\bm{e}\). While exact recovery of \(x^*\) via strong (and often impractical) structural assumptions on \(\bm{A}\) or \(x^*\) (for example, restricted isometry, sparsity) is well studied, recoverability for arbitrary \(\bm{A}\) and \(x^*\) remains open. Our main result shows that the best that one can hope to recover is \(x^* + \ker(\bm{U})\), where \(\bm{U}\) is the unique projection matrix onto the intersection of rowspaces of all possible submatrices of \(\bm{A}\) obtained by deleting \(2q\) rows. Moreover, we prove that every \(x\) that minimizes the \(\ell\_0\)-norm of \(\bm{y} - \bm{A} x\) lies in \(x^* + \ker(\bm{U})\), which then gives a constructive approach to recover this set.