Projects per year
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 language | English |
---|---|
Pages (from-to) | 171–193 |
Number of pages | 23 |
Journal | Journal of the Operations Research Society of China |
Volume | 2 |
Issue number | 2 |
Early online date | 24 May 2014 |
DOIs | |
Publication status | Published - 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.Projects
- 1 Finished
-
Foundation and Reweighted Algorithms for Sparsest Points of Convex Sets with Application to Data Processing
Zhao, Y.-B. (Principal Investigator)
Engineering & Physical Science Research Council
18/04/13 → 31/05/15
Project: Research Councils