Sparse solutions to linear systems of equations affected by noise or modeling errors are considered. In contrast to standard \(\ell _2-\ell _0\) , we consider a \(\ell _1-\ell _0\) formulation to better handle outliers in the data. A sparse solution to the system that minimizes the \(\ell _1\) -norm of the residual error is sought. Sparsity is controlled using a \(\ell _0\) -norm term weighted by a positive parameter. A detailed study of the local and global minimizers is given. A simple necessary condition for global optimality and conditions for monitoring the sparsity level of the minimizers is derived. An upper bound on the maximum entry of a globally optimal solution permits an exact MIP formulation with constraints derived from the analysis.
