## Equivalence and Strong Equivalence between Sparsest and Least $\ell_1hBcNorm Nonnegative Solutions of Linear Systems and Their Application Many practical problems can be formulated as$\ell_0$-minimization problems with nonnegativity constraints, which seek the sparsest nonnegative solutions to underdetermined linear systems. Recent study indicates that$\ell_1$-minimization is efficient for solving some classes of$\ell_0$-minimization problems. From a mathematical point of view, however, the understanding of the relationship between$\ell_0$- and$\ell_1$-minimization remains incomplete. In … Read more ## Equivalence and Strong Equivalence between Sparsest and Least l1-Norm Nonnegative Solutions of Linear Systems and Their Application Many practical problems can be formulated as$\ell_0$-minimization problems with nonnegativity constraints, which seek the sparsest nonnegative solutions to underdetermined linear systems. Recent study indicates that$\ell_1$-minimization is efficient for solving some classes of$\ell_0$-minimization problems. From a mathematical point of view, however, the understanding of the relationship between$\ell_0$- and$\ell_1$-minimization remains incomplete. In … Read more ## RSP-Based Analysis for Sparsest and Least$\ell_1hBcNorm Solutions to Underdetermined Linear Systems

Recently, the worse-case analysis, probabilistic analysis and empirical justification have been employed to address the fundamental question: When does $\ell_1$-minimization find the sparsest solution to an underdetermined linear system? In this paper, a deterministic analysis, rooted in the classic linear programming theory, is carried out to further address this question. We first identify a necessary … Read more

## New and Improved Conditions for Uniqueness of Sparsest Solutions of Underdetermined Linear Systems

The uniqueness of sparsest solutions of underdetermined linear systems plays a fundamental role in the newly developed compressed sensing theory. Several new algebraic concepts, including the sub-mutual coherence, scaled mutual coherence, coherence rank, and sub-coherence rank, are introduced in this paper in order to develop new and improved sufficient conditions for the uniqueness of sparsest … Read more