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-minim...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 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 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 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 new and broad understanding of the equivalence and the strong equivalence between l0-and l1-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.展开更多
基金supported by the Engineering and Physical Sciences Research Council(No.K00946X/1)was partially supported by the National Natural Science Foundation of China(No.11301016).
文摘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 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 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 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 new and broad understanding of the equivalence and the strong equivalence between l0-and l1-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.
