Equivalence and strong equivalence between the sparsest and least _1-norm nonnegative solutions of linear systems and their applications

DOI10.1007/S40305-014-0043-1zbMATH Open1308.90100arXiv1312.4163OpenAlexW2025482263MaRDI QIDQ489110FDOQ489110

Authors: Yun-Bin Zhao 

Publication date: 27 January 2015

Published in: Journal of the Operations Research Society of China (Search for Journal in Brave)

Abstract: 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 some classes of 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 discuss several theoretical questions associated with these two problems. For instance, how to completely characterize the uniqueness of least l1-norm nonnegative solutions to a linear system, and is there any alternative matrix property that is different from existing ones, and can fully characterize the uniform recovery of K-sparse nonnegative vectors? We prove that the fundamental strict complementarity theorem of linear programming can yield a necessary and sufficient condition for a linear system to have 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 broad understanding of the relationship between l0- and l1-minimization. Motivated by these results, we introduce the concept of the `RSP of order K' that turns out to be a full characterization of the uniform recovery of K-sparse nonnegative vectors. This concept also enables us to develop certain conditions for the non-uniform recovery of sparse nonnegative vectors via the so-called weak range space property.

Full work available at URL: https://arxiv.org/abs/1312.4163

Recommendations

• scientific article; zbMATH DE number 6746123
• Uniqueness conditions for the sparsest solution of linear systems
• Nonuniqueness of solutions of a class of \(\ell_0\)-minimization problems
• Equivalence of minimal \(\ell _{0}\)- and \(\ell _{p }\)-norm solutions of linear equalities, inequalities and linear programs for sufficiently small \(p\)
• For most large underdetermined systems of linear equations the minimal 𝓁₁‐norm solution is also the sparsest solution

zbMATH Keywords

linear programmingunderdetermined linear systemstrict complementaritynonuniform recoveryrange space propertysparsest nonnegative solutionuniform recovery

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Linear programming (90C05) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Sampling theory in information and communication theory (94A20)

Cites Work

• A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization, and continuation
• Title not available (Why is that?)
• Enhancing sparsity by reweighted \(\ell _{1}\) minimization
• Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ ¹ minimization
• Compressive sampling
• Decoding by Linear Programming
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Sparse and redundant representations. From theory to applications in signal and image processing.
• From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
• Learning the parts of objects by non-negative matrix factorization
• Compressed sensing
• On Sparse Representations in Arbitrary Redundant Bases
• Greed is Good: Algorithmic Results for Sparse Approximation
• Reweighted \(\ell_1\)-minimization for sparse solutions to underdetermined linear systems
• Sparse nonnegative solution of underdetermined linear equations by linear programming
• On verifiable sufficient conditions for sparse signal recovery via \(\ell_{1}\) minimization
• The use of the optimal partition in a linear programming solution for postoptimal analysis
• Iteratively reweighted least squares minimization for sparse recovery
• Sparse Approximate Solutions to Linear Systems
• Sparse representations in unions of bases
• The restricted isometry property and its implications for compressed sensing
• Minimum-support solutions of polyhedral concave programs^*
• Parsimonious least norm approximation
• Counting the faces of randomly-projected hypercubes and orthants, with applications
• Title not available (Why is that?)
• Covariance-Preconditioned Iterative Methods for Nonnegatively Constrained Astronomical Imaging
• On the Uniqueness of Nonnegative Sparse Solutions to Underdetermined Systems of Equations
• Nonnegative Matrix Factorization Based on Alternating Nonnegativity Constrained Least Squares and Active Set Method
• Sparse Recovery of Nonnegative Signals With Minimal Expansion
• Mathematical Programming for Data Mining: Formulations and Challenges
• Theory of compressive sensing via \(\ell_1\)-minimization: a non-RIP analysis and extensions
• An approximation theory of matrix rank minimization and its application to quadratic equations
• Verifiable conditions of \(\ell_{1}\)-recovery for sparse signals with sign restrictions
• Nonnegativity constraints in numerical analysis
• A Unique “Nonnegative” Solution to an Underdetermined System: From Vectors to Matrices
• Nonnegative matrix factorization for spectral data analysis
• A generalized uncertainty principle and sparse representation in pairs of bases
• Nonuniform sparse recovery with subgaussian matrices
• An analysis of degeneracy
• On sparse representation in pairs of bases

Cited In (21)

• Equivalence of minimal \(\ell _{0}\)- and \(\ell _{p }\)-norm solutions of linear equalities, inequalities and linear programs for sufficiently small \(p\)
• Nonuniqueness of solutions of a class of \(\ell_0\)-minimization problems
• Optimality analysis on partial \(l_1\)-minimization recovery
• Uniqueness of the minimal \(l_1\)-norm solution to the monotone linear complementarity problem
• Stability analysis of a class of sparse optimization problems
• On the Uniqueness of Nonnegative Sparse Solutions to Underdetermined Systems of Equations
• The sparsest solution to the system of absolute value equations
• Nonnegative partial \(s\)-goodness for the equivalence of a 0-1 linear program to weighted linear programming
• \(k\) block sparse vector recovery via block \(\ell_1-\ell_2\) minimization
• Title not available (Why is that?)
• \(k\)-sparse vector recovery via truncated \(\ell_1 -\ell_2\) local minimization
• Constructing New Weighted ℓ₁-Algorithms for the Sparsest Points of Polyhedral Sets
• Uniqueness conditions for a class of \(\ell_{0}\)-minimization problems
• Solution uniqueness of convex piecewise affine functions based optimization with applications to constrained \(\ell_1\) minimization
• 1-bit compressive sensing: reformulation and RRSP-based sign recovery theory
• Non-negative sparse regression and column subset selection with \(L_1\) error
• A survey on compressive sensing: classical results and recent advancements
• k-Sparse Vector Recovery via $$\ell _1-\alpha \ell _2$$ Local Minimization
• Uniqueness conditions for the sparsest solution of linear systems
• The nonnegative zero-norm minimization under generalized \(Z\)-matrix measurement
• Weak stability of \(\ell_1\)-minimization methods in sparse data reconstruction

This page was built for publication: Equivalence and strong equivalence between the sparsest and least \(\ell _1\)-norm nonnegative solutions of linear systems and their applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q489110)