A Sparse and Non-Negative Solution of Ax=b is Necessarily Unique
March 30th, 2008
ICASSP, Las-Vegas.

An under-determined linear system of equations Ax = b with non-negativity constraint 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. It is further shown that A undergoes a conditioning stage with some degrees of freedom, which may be used to improve the coherence measure and strengthen the claimed result.

Joint work with Michael Zibulevsky and Freddy Bruckstein.