Equivalence and strong equivalence between the sparsest and least _1-norm nonnegative solutions of linear systems and their applications
From MaRDI portal
(Redirected from Publication:489110)
Equivalence and strong equivalence between the sparsest and least \(\ell 1\)-norm nonnegative solutions of linear systems and their applications
Equivalence and strong equivalence between the sparsest and least \(\ell 1\)-norm nonnegative solutions of linear systems and their applications
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.
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 𝓁1‐norm solution is also the sparsest solution
Cites work
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 1215260 (Why is no real title available?)
- A Unique “Nonnegative” Solution to an Underdetermined System: From Vectors to Matrices
- A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization, and continuation
- A generalized uncertainty principle and sparse representation in pairs of bases
- An analysis of degeneracy
- An approximation theory of matrix rank minimization and its application to quadratic equations
- Compressed sensing
- Compressive sampling
- Counting the faces of randomly-projected hypercubes and orthants, with applications
- Covariance-Preconditioned Iterative Methods for Nonnegatively Constrained Astronomical Imaging
- Decoding by Linear Programming
- Enhancing sparsity by reweighted \(\ell _{1}\) minimization
- From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
- Greed is Good: Algorithmic Results for Sparse Approximation
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- Iteratively reweighted least squares minimization for sparse recovery
- Learning the parts of objects by non-negative matrix factorization
- Mathematical Programming for Data Mining: Formulations and Challenges
- Minimum-support solutions of polyhedral concave programs*
- Nonnegative Matrix Factorization Based on Alternating Nonnegativity Constrained Least Squares and Active Set Method
- Nonnegative matrix factorization for spectral data analysis
- Nonnegativity constraints in numerical analysis
- Nonuniform sparse recovery with subgaussian matrices
- On Sparse Representations in Arbitrary Redundant Bases
- On sparse representation in pairs of bases
- On the Uniqueness of Nonnegative Sparse Solutions to Underdetermined Systems of Equations
- On verifiable sufficient conditions for sparse signal recovery via \(\ell_{1}\) minimization
- Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimization
- Parsimonious least norm approximation
- Reweighted \(\ell_1\)-minimization for sparse solutions to underdetermined linear systems
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Sparse Approximate Solutions to Linear Systems
- Sparse Recovery of Nonnegative Signals With Minimal Expansion
- Sparse and redundant representations. From theory to applications in signal and image processing.
- Sparse nonnegative solution of underdetermined linear equations by linear programming
- Sparse representations in unions of bases
- The restricted isometry property and its implications for compressed sensing
- The use of the optimal partition in a linear programming solution for postoptimal analysis
- Theory of compressive sensing via _1-minimization: a non-RIP analysis and extensions
- Verifiable conditions of \(\ell_{1}\)-recovery for sparse signals with sign restrictions
Cited in
(21)- Weak stability of \(\ell_1\)-minimization methods in sparse data reconstruction
- 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₁-minimization recovery
- Uniqueness of the minimal \(l_1\)-norm solution to the monotone linear complementarity problem
- On the Uniqueness of Nonnegative Sparse Solutions to Underdetermined Systems of Equations
- Stability analysis of a class of sparse optimization problems
- 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
- scientific article; zbMATH DE number 6746123 (Why is no real title available?)
- \(k\)-sparse vector recovery via truncated \(\ell_1 -\ell_2\) local minimization
- Constructing New Weighted ℓ1-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
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)
