On the Uniqueness of Nonnegative Sparse Solutions to Underdetermined Systems of Equations

An underdetermined linear system of equations Ax = b with nonnegativity constraint x >= 0 is considered. It is shown that for matrices A with a row-span intersecting the positive orthant, if this problem admits a sufficiently sparse solution, it is necessarily unique. The bound on the required sparsity depends on a coherence property of the matrix A. This coherence measure can be improved by applying a conditioning stage on A, thereby strengthening the claimed result. The obtained uniqueness theorem relies on an extended theoretical analysis of the l(0) - l(1) equivalence developed here as well, considering a matrix A with arbitrary column norms, and an arbitrary monotone element-wise concave penalty replacing the l(1)-norm objective function. Finally, from a numerical point of view, a greedy algorithm-a variant of the matching pursuit-is presented, such that it is guaranteed to find this sparse solution. It is further shown how this algorithm can benefit from well-designed conditioning of A.