Abstract:

Many practical problems can be formulated as ‘0-minimization problems
with nonnegativity constraints, which seek the sparsest nonnegative solutions
to underdetermined linear systems. Recent study indicates that l_1-minimization is
efficient for solving ‘0-minimization problems. From a mathematical point of view,
however, the understanding of the relationship between l_0- and l_1-minimization
remains incomplete. In this paper, we further address several theoretical questions
associated with these two problems. We prove that the fundamental strict complementarity
theorem of linear programming can yield a necessary and sufficient
condition for a linear system to admit a unique least  l_1-norm nonnegative solution.
This condition leads naturally to the so-called range space property (RSP) and the

"full-column-rank’’ property, which altogether provide a new and broad understanding
of the equivalence and the strong equivalence between l_0- and l_1-minimization.
Motivated by these results, we introduce the concept of ‘‘RSP of order K’’
that turns out to be a full characterization of uniform recovery of all K-sparse
nonnegative vectors. This concept also enables us to develop a nonuniform recovery
theory for sparse nonnegative vectors via the so-called weak range space property.

Key words: Strict complementarity ,  Linear programming , Underdetermined
linear system ,  Sparsest nonnegative solution ,  Range space property , Uniform recovery ,  Nonuniform recovery