The Basis Pursuit as a Set Selector

Success in the solution of under-constrained problems where sparsity is an appropriate regularization is typically judged by comparing the solution from whatever algorithm is used with the true result. This paper puts forth the idea that this is an unnecessarily high bar since the reason why the problem is underdetermined is because the location of the non-zero entries in the solution vector are unknown, although their number must be no larger than the constraints since otherwise the problem is ill-posed. Provided one is able to operate offline what’s needed from a sparse solver is, therefore, that it provides a subset of the original unknowns no larger than the number of constraints, rendering the problem fully constrained. One may wonder how the solver can offer a solution that can be improved, and the answer is that this is possible because the problem tackled (linear) differs from the real one (nonlinear). This paper focuses on the Basis Pursuit and shows how a set selector implementation can offer improvements in performance for moderate to large values of damage severity.