  


Equivalence and Strong Equivalence between Sparsest and Least l1Norm Nonnegative Solutions of Linear Systems and Their Application
YunBin 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 socalled range space property (RSP) and the `fullcolumnrank' 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 nonuniform recovery of sparse nonnegative vectors via the socalled weak range space property. Keywords: Linear programming, Underdetermined linear system, Sparsest nonnegativesolution, Range space property, Uniform (nonuniform) 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/2013 Modify/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  