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

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.

Newton-Type Optimal Thresholding Algorithms for Sparse Optimization Problems

Sparse signals can be possibly reconstructed by an algorithm which merges a traditional nonlinear optimization method and a certain thresholding technique.Different from existing thresholding methods,a novel thresholding technique referred to as the optimal k-thresholding was recently proposed by Zhao(SIAM J Optim 30(1):31-55,2020).This technique simultaneously performs the minimization of an error metric for the problem and thresholding of the iterates generated by the classic gradient method.In this paper,we propose the so-called Newton-type optimal k-thresholding(NTOT)algorithm which is motivated by the appreciable performance of both Newton-type methods and the optimal k-thresholding technique for signal recovery.The guaranteed performance(including convergence)of the proposed algorithms is shown in terms of suitable choices of the algorithmic parameters and the restricted isometry property(RIP)of the sensing matrix which has been widely used in the analysis of compressive sensing algorithms.The simulation results based on synthetic signals indicate that the proposed algorithms are stable and efficient for signal recovery.