View article

An underdetermined linear system of equations Ax = b with nonnegativity constraint x ges 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 lscr ₀ - lscr ₁ equivalence developed here as well, considering a matrix A with arbitrary column norms, and an arbitrary monotone element-wise concave penalty replacing the lscr ₁ -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 …