Necessary and sufficient conditions of solution uniqueness in ℓ1 minimization

Hui Zhang, Wotao Yin, Lizhi ChengarXiv 2012 · arXiv · OpenReview

Abstract

This paper establishes that the solutions to a broad class of convex $\ell_1$ minimization problems are unique if and only if a specific set of conditions is satisfied. This unified result applies to the Basis Pursuit (BP) model, Basis Pursuit Denoising (BPDN), the Lasso, and other models that either minimize a strictly convex loss function $f(Ax-b)$ or impose a constraint $f(Ax-b) \leq \sigma$. We prove that for a given solution $x^*$, with support $I = \text{supp}(x^*)$ and signs $s = \text{sign}(x^*_I)$, $x^*$ is the unique solution if and only if the submatrix $A_I$ has full column rank and there exists a dual vector $y$ such that $A_I^T y = s$ and $|a_i^T y| < 1$ for all $i \notin I$. While this condition was previously known to be sufficient for Basis Pursuit, this work demonstrates its necessity and its broad applicability across the $\ell_1$ minimization landscape.

Introduction

In the fields of compressive sensing, machine learning, and statistical signal processing, $\ell_1$ minimization is the standard tool for recovering sparse signals from underdetermined linear systems. Whether through the Basis Pursuit model (finding the sparsest exact solution) or the Lasso (balancing data fidelity with sparsity), the utility of these methods hinges on a fundamental question: is the recovered solution unique?

If multiple solutions exist, the reliability of the recovered signal is compromised, as the specific features identified by the algorithm may be arbitrary. Historically, researchers have relied on sufficient conditions for uniqueness, such as the Restricted Isometry Property (RIP) or the Null Space Property (NSP). However, these conditions are often overly conservative and difficult to verify. This paper fills a critical gap by providing a unified condition that is both necessary and sufficient for uniqueness across the most common $\ell_1$ optimization frameworks.

The Unified Uniqueness Condition

The core contribution of this research is the formalization of Condition 1. For a candidate solution $x^*$, let $I$ denote the indices of its non-zero entries (its support) and $s$ denote the signs of those entries. The solution $x^*$ is unique if and only if:

  1. Rank Condition: The submatrix $A_I$ (formed by the columns of $A$ corresponding to the support $I$) has full column rank.
  2. Dual Certificate: There exists a dual vector $y$ such that $A_I^T y = s$ and the remaining correlations are strictly bounded, i.e., $|a_i^T y| < 1$ for all $i \notin I$.

While the sufficiency of this condition for the Basis Pursuit model was previously established, this paper provides the first rigorous proof of its necessity. Furthermore, the authors demonstrate that this exact same condition governs uniqueness for more complex models, including Lasso and BPDN, provided the loss function $f(Ax-b)$ is strictly convex.

Theoretical Framework and Generalization

The authors employ convex analysis, strong duality, and strict complementarity to bridge the gap between different $\ell_1$ models. A pivotal insight in their proof is a lemma regarding the geometry of the solution set for generalized models. They show that for any two solutions $x_1$ and $x_2$ to a problem involving a strictly convex loss $f(Ax-b)$:

  • The predictions are identical: $Ax_1 = Ax_2$.
  • The $\ell_1$ norms are identical: $\|x_1\|_1 = \|x_2\|_1$.

This "constant prediction" property allows the authors to reduce the uniqueness analysis of complex, unconstrained problems (like Lasso) to the analysis of a simpler, constrained Basis Pursuit-style problem. By using a perturbation argument on the dual linear program, they prove that the strict inequality $|a_i^T y| < 1$ is not just a helpful buffer, but a mathematical requirement for a unique solution.

Practical Implications and Verification

Beyond theoretical interest, these findings offer practical tools for practitioners. The paper refutes several prior assumptions in the literature, including a previously proposed necessary condition for Lasso that the authors disprove with a concrete counter-example.

To aid in numerical verification, the authors suggest that the uniqueness condition can be checked using standard optimization outputs. For instance, interior-point methods for linear programming naturally produce dual solutions that can be tested against Condition 1. Additionally, the authors propose a specific convex program (Equation 11 in the paper) that can be solved via the Alternating Direction Method of Multipliers (ADMM) to determine if a valid dual vector $y$ exists for a given $x^*$.

Conclusion

This work provides a definitive answer to the question of uniqueness in $\ell_1$ minimization. By establishing a single condition that is both necessary and sufficient, it provides a foundational guarantee for sparse recovery. While the results rely on the strict convexity of the error term, they cover the vast majority of practical applications in signal processing and statistics. Future work may explore the scalability of numerical verification for extremely large-scale systems and the implications for non-strictly convex loss functions.

Summary updated

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)\leq\sigma$, where $f$ is a strictly convex function. For these models, this paper proves that, given a solution $x^*$ and defining $I=\supp(x^*)$ and $s=\sign(x^*_I)$, $x^*$ is the unique solution if and only if $A_I$ has full column rank and there exists $y$ such that $A_I^Ty=s$ and $|a_i^Ty|_\infty<1$ for $i\not\in 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.
BibTeX
@misc{zhang2012necessary,
  author = {Hui Zhang and Wotao Yin and Lizhi Cheng},
  title = {{Necessary and sufficient conditions of solution uniqueness in ℓ1 minimization}},
  year = {2012},
  eprint = {1209.0652},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1209.0652},
}
Figure