Necessary and sufficient conditions of solution uniqueness in 1-norm minimization

DOI10.1007/S10957-014-0581-ZzbMATH Open1308.65102arXiv1209.0652OpenAlexW3098520355MaRDI QIDQ2260650FDOQ2260650

Authors: Hui Zhang, Wotao Yin, Li-zhi Cheng 

Publication date: 11 March 2015

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

Abstract: This paper shows that the solutions to various convex $el{l}_1$ minimization problems are emph{unique} if and only if a common set of conditions are satisfied. This result applies broadly to the basis pursuit model, basis pursuit denoising model, Lasso model, as well as other $el{l}_1$ models that either minimize $f(Ax-b)$ or impose the constraint $f(Ax-b)leqsigma$, where $f$ is a strictly convex function. For these models, this paper proves that, given a solution $x^{*}$ and defining $I=supp(x^{\ast })$ and $s=sign(x_I^{\ast })$, $x^{*}$ is the unique solution if and only if $A_I$ has full column rank and there exists $y$ such that $A_I^{T}y=s$ and $|a_i^{T}y{|}_{i}nfty<1$ for $iotinI$. This condition is previously known to be sufficient for the basis pursuit model to have a unique solution supported on $I$. Indeed, it is also necessary, and applies to a variety of other $el{l}_1$ models. The paper also discusses ways to recognize unique solutions and verify the uniqueness conditions numerically.

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

Recommendations

• On the solution uniqueness characterization in the L1 norm and polyhedral gauge recovery
• Solution uniqueness of convex piecewise affine functions based optimization with applications to constrained \(\ell_1\) minimization
• A necessary and sufficient condition for exact sparse recovery by \(\ell_1\) minimization
• One condition for solution uniqueness and robustness of both \(\ell_1\)-synthesis and \(\ell_1\)-analysis minimizations
• On the uniqueness of the optimal solution in the linear programming

zbMATH Keywords

lassostrict complementarity\(\ell_1\) minimizationbasis pursuitsolution uniqueness

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25)

Cites Work

• Least angle regression. (With discussion)
• Title not available (Why is that?)
• Atomic Decomposition by Basis Pursuit
• Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ ¹ minimization
• Decoding by Linear Programming
• The Lasso problem and uniqueness
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
• Compressed sensing
• Title not available (Why is that?)
• Necessary and sufficient conditions for linear convergence of \(\ell^1\)-regularization
• Compressed sensing and best \(k\)-term approximation
• On Sparse Representations in Arbitrary Redundant Bases
• Recovery of Exact Sparse Representations in the Presence of Bounded Noise
• Uncertainty principles and ideal atomic decomposition
• A Probabilistic and RIPless Theory of Compressed Sensing
• Recovery of Short, Complex Linear Combinations Via&lt;tex&gt;$ell _1$&lt;/tex&gt;Minimization
• Constructing Test Instances for Basis Pursuit Denoising
• Sensitivity Analysis for Mean-Variance Portfolio Problems
• Simple bounds for recovering low-complexity models
• Title not available (Why is that?)
• Theory of compressive sensing via \(\ell_1\)-minimization: a non-RIP analysis and extensions
• A generalized uncertainty principle and sparse representation in pairs of bases
• Convergence behavior of interior-point algorithms
• A necessary and sufficient condition for exact sparse recovery by \(\ell_1\) minimization

Cited In (30)

• LASSO Reloaded: A Variational Analysis Perspective with Applications to Compressed Sensing
• Bias versus non-convexity in compressed sensing
• Maximal solutions of sparse analysis regularization
• Isolated calmness of solution mappings and exact recovery conditions for nuclear norm optimization problems
• A smoothed \(l_0\)-norm and \(l_1\)-norm regularization algorithm for computed tomography
• Square root LASSO: well-posedness, Lipschitz stability, and the tuning trade-off
• The generalized Lasso problem and uniqueness
• One condition for solution uniqueness and robustness of both \(\ell_1\)-synthesis and \(\ell_1\)-analysis minimizations
• Identifying the source term in the potential equation with weighted sparsity regularization
• On the Probabilistic Cauchy Theory for Nonlinear Dispersive PDEs
• Local and global convergence of a general inertial proximal splitting scheme for minimizing composite functions
• \(k\)-sparse vector recovery via truncated \(\ell_1 -\ell_2\) local minimization
• Necessary and Sufficient Conditions for Noiseless Sparse Recovery via Convex Quadratic Splines
• Solution uniqueness of convex piecewise affine functions based optimization with applications to constrained \(\ell_1\) minimization
• The homotopy method revisited: computing solution paths of \(\ell_1\)-regularized problems
• An introduction to compressed sensing
• Quadratic growth conditions and uniqueness of optimal solution to Lasso
• A survey on compressive sensing: classical results and recent advancements
• Box Constraints and Weighted Sparsity Regularization for Identifying Sources in Elliptic PDEs
• k-Sparse Vector Recovery via $$\ell _1-\alpha \ell _2$$ Local Minimization
• Accelerated iterative hard thresholding algorithm for \(l_0\) regularized regression problem
• Regularisation, optimisation, subregularity
• On the sparsity of Lasso minimizers in sparse data recovery
• On uniqueness guarantees of solution in convex regularized linear inverse problems
• Safe feature elimination for non-negativity constrained convex optimization
• Sufficient conditions for the uniqueness of solution of the weighted norm minimization problem
• On the solution uniqueness characterization in the L1 norm and polyhedral gauge recovery
• Uniqueness in nuclear norm minimization: flatness of the nuclear norm sphere and simultaneous polarization
• Existence and uniqueness of solutions to the norm minimum problem on digraphs
• Weak stability of \(\ell_1\)-minimization methods in sparse data reconstruction

Uses Software

• PDCO
• L1TestPack

This page was built for publication: Necessary and sufficient conditions of solution uniqueness in 1-norm minimization

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