Optimization Online


Equivalence and Strong Equivalence between Sparsest and Least $\ell_1$-Norm Nonnegative Solutions of Linear Systems and Their Application

Y Zhao (y.zhao.2***at***bham.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 nonnegative solution, Range space property, Uniform (nonuniform) Recovery

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Applications -- Science and Engineering

Category 3: Linear, Cone and Semidefinite Programming (Linear Programming )


Download: [PDF]

Entry Submitted: 12/19/2013
Entry Accepted: 12/19/2013
Entry Last Modified: 12/19/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society