- Equivalence and Strong Equivalence between Sparsest and Least l1-Norm Nonnegative Solutions of Linear Systems and Their Application Yun-Bin Zhao(y.zhao.2bham.ac.uk) Abstract: 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. Keywords: Linear programming, Underdetermined linear system, Sparsest nonnegativesolution, Range space property, Uniform (non-uniform) recovery Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Category 2: Convex and Nonsmooth Optimization (Convex Optimization ) Category 3: Global Optimization Citation: Download: [PDF]Entry Submitted: 12/19/2013Entry Accepted: 12/19/2013Entry Last Modified: 12/19/2013Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.