Necessary and sufficient conditions of solution uniqueness in ${\ell }_1$ minimization

Abstract

This paper shows that the solutions to various convex ${\ell }_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 ${\ell }_1$ models that either minimize $f(Ax-b)$ or impose the constraint $f(Ax-b)\le \sigma$, where $f$ is a strictly convex function. For these models, this paper proves that, given a solution $x^{\ast }$ and defining $I=\supp(x^*)$ and $s=\sign(x^*_I)$, $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{|}_{\infty }<1$ for $i\notin I$. 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 ${\ell }_1$ models. The paper also discusses ways to recognize unique solutions and verify the uniqueness conditions numerically.

6 pages; revised version; submitted

Cited by in corpus (5)

• One condition for solution uniqueness and robustness of both l1-synthesis and l1-analysis minimizations
• Local and Global Convergence of a General Inertial Proximal Splitting Scheme
• Regularisation, optimisation, subregularity
• On the best choice of Lasso program given data parameters
• Safe Feature Elimination for Non-Negativity Constrained Convex Optimization