Equivalence and Strong Equivalence between Sparsest and Least l1-Norm Nonnegative Solutions of Linear Systems and Their Application

Many practical problems can be formulated as $\ell_0$-minimization problems with nonnegativity constraints, which seek the sparsest nonnegative solutions to underdetermined linear systems. Recent study indicates that $\ell_1$-minimization is efficient for solving some classes of $\ell_0$-minimization problems. From a mathematical point of view, however, the understanding of the relationship between $\ell_0$- and $\ell_1$-minimization remains incomplete. In this paper, we further discuss several theoretical questions associated with these two problems. For instance, how to completely characterize the uniqueness of least $\ell_1$-norm nonnegative solutions to a linear system, and is there any alternative matrix property that is different from existing ones, and can fully characterize the uniform recovery of $K$-sparse nonnegative vectors? We prove that the fundamental strict complementarity theorem of linear programming can yield a necessary and sufficient condition for a linear system to have a unique least $\ell_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 broad understanding of the relationship between $ \ell_0$- and $\ell_1$-minimization. Motivated by these results, we introduce the concept of the `RSP of order $K$' that turns out to be a full characterization of the uniform recovery of $K$-sparse nonnegative vectors. This concept also enables us to develop certain conditions for the non-uniform recovery of sparse nonnegative vectors via the so-called weak range space property.

Article

Download

View Equivalence and Strong Equivalence between Sparsest and Least l1-Norm Nonnegative Solutions of Linear Systems and Their Application