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

DOI10.1007/S10957-014-0581-ZMaRDI QIDQ2260650zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

\(\ell_1\) minimizationbasis pursuitlassosolution uniquenessstrict complementarity

Mathematics Subject Classification ID

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

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^{\ast }$ and defining $I=supp(x^{\ast })$ and $s=sign(x_I^{\ast })$, $x^{\ast }$ 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.

Review text

With a given solution to a 1-norm minimization problem, based on the fact that a pair of feasible primal-dual linear programs has strict complementary solutions, the authors provide a necessary and sufficient condition for guaranteeing recovering that solution uniquely. Some ways on numerically recognizing unique solutions and verifying solution uniqueness are discussed.

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 _1 minimization
• A necessary and sufficient condition for exact sparse recovery by \(\ell_1\) minimization
• One condition for solution uniqueness and robustness of both _1-synthesis and _1-analysis minimizations
• On the uniqueness of the optimal solution in the linear programming

Cites work

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

Cited in

(35)

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

Describes a project that uses

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)