Sparse non-negative solution of a linear system of equations is unique

We consider an underdetermined linear system of equations Ax = b with non-negative entries of A and b, and the solution x being also required to be non-negative. We show that if there exists a sufficiently sparse solution to this problem, it is necessarily unique. Furthermore, we present a greedy algorithm - a variant of the matching pursuit - that is guaranteed to find this sparse solution. The result mentioned above is obtained by extending the existing theoretical analysis of the basis pursuit problem, i.e. min ||x|| 1 s.t. Ax = b, by studying conditions for perfect recovery of sparse enough solutions. Considering a matrix A with arbitrary column norms, and an arbitrary monotone element-wise concave penalty replacing the lscr 1 -norm objective function, we generalize known equivalence results, and use those to derive the above uniqueness claim.