Let $\mathbf{A}\in\mathbb{R}^{m\times n}$ be an arbitrary, known matrix and $\mathbf{e}$ a $q$-sparse adversarial vector. Given $\mathbf{y}=\mathbf{A}\mathbf{x}^*+\mathbf{e}$ and $q$, we seek the smallest robust solution set containing $\mathbf{x}^*$ that is uniformly recoverable from $\mathbf{y}$ without knowing $\mathbf{e}.$ While exact recovery of $\mathbf{x}^*$ via strong (and often impractical) structural assumptions on $\mathbf{A}$ or $\mathbf{x}^*$ (e.g., restricted isometry, sparsity) is well studied, recoverability for arbitrary $\mathbf{A}$ and $\mathbf{x}^*$ remains open. Our main result shows that the smallest robust solution set is $\mathbf{x}^* + \ker(\mathbf{U}),$ where $\mathbf{U}$ is the unique projection matrix onto the intersection of rowspaces of all possible submatrices of $\mathbf{A}$ obtained by deleting $2q$ rows. Moreover, we prove that every $\mathbf{x}$ that minimizes the $\ell_0$-norm of $\mathbf{y} - \mathbf{A} \mathbf{x}$ lies in $\mathbf{x}^* + \ker(\mathbf{U})$, which then gives a constructive approach to recover this set.
Alexandre Reiffers-Masson has developed a research trajectory grounded in applied mathematics, optimisation, and learning, with a strong connection to real-world systems and industrial applications. After completing his PhD at Inria on game-theoretic models applied to online social networks, he worked as a research engineer at SafranTech, where he studied predictive maintenance policy strategies using stochastic models and reliability theory. From 2018-2020, he pursued a postdoctoral position at IISc Bangalore India, focusing on information design and decision-making in IoT and industrial systems. Since joining IMT Atlantique as associate professor, in March 2020, his research has focused on adversarial learning and distributed learning for network robustness, fault detection using machine learning (time-series segmentation and Novel class discovery), stochastic processes for the study of distributed ledgers and stochastic optimisation problems for resource allocation problems in cloud, defence and cyber-security. He is also the coordinator of two international projects that bridge AI, distributed systems, and security.