Equivalence and Strong Equivalence Between the Sparsest and Least ℓ1-Norm Nonnegative Solutions of Linear Systems and Their Applications

Yun-Bin Zhao

Research output: Contribution to journalArticlepeer-review

13 Citations (Scopus)
94 Downloads (Pure)

Abstract

Many practical problems can be formulated as ℓ0-minimization problems with nonnegativity constraints, which seek the sparsest nonnegative solutions to underdetermined linear systems. Recent study indicates that ℓ1-minimization is efficient for solving ℓ0-minimization problems. From a mathematical point of view, however, the understanding of the relationship between ℓ0- and ℓ1-minimization remains incomplete. In this paper, we further address several theoretical questions associated with these two problems. We prove that the fundamental strict complementarity theorem of linear programming can yield a necessary and sufficient condition for a linear system to admit a unique least ℓ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 new and broad understanding of the equivalence and the strong equivalence between ℓ0- and ℓ1-minimization. Motivated by these results, we introduce the concept of “RSP of order K” that turns out to be a full characterization of uniform recovery of all K-sparse nonnegative vectors. This concept also enables us to develop a nonuniform recovery theory for sparse nonnegative vectors via the so-called weak range space property.
Original languageEnglish
Pages (from-to)171–193
Number of pages23
JournalJournal of the Operations Research Society of China
Volume2
Issue number2
Early online date24 May 2014
DOIs
Publication statusPublished - Jun 2014

Keywords

  • Strict complementarity
  • Linear programming
  • Underdetermined linear system
  • Sparsest nonnegative solution
  • Range space property
  • Uniform recovery
  • Nonuniform recovery

Fingerprint

Dive into the research topics of 'Equivalence and Strong Equivalence Between the Sparsest and Least ℓ1-Norm Nonnegative Solutions of Linear Systems and Their Applications'. Together they form a unique fingerprint.

Cite this