{
  "id": "1312.4163",
  "version": "v1",
  "published": "2013-12-15T16:26:30.000Z",
  "updated": "2013-12-15T16:26:30.000Z",
  "title": "Equivalence and Strong Equivalence between Sparsest and Least $\\ell_1$-Norm Nonnegative Solutions of Linear Systems and Their Application",
  "authors": [
    "Yun-Bin Zhao"
  ],
  "categories": [
    "math.OC"
  ],
  "abstract": "Many practical problems can be formulated as l0-minimization problems with nonnegativity constraints, which seek the sparsest nonnegative solutions to underdetermined linear systems. Recent study indicates that l1-minimization is efficient for solving some classes of l0-minimization problems. From a mathematical point of view, however, the understanding of the relationship between l0- and l1-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 l1-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 l1-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 l0- and l1-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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-12-15T16:26:30.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "linear system",
      "norm nonnegative solutions",
      "strong equivalence",
      "l1-norm nonnegative solution",
      "k-sparse nonnegative vectors"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "inspire": 1269568,
      "adsabs": "2013arXiv1312.4163Z"
    }
  }
}