Sparse Optimization Theory and Methods

Chapter 2

Uniqueness of Solutions to ℓ₁-Minimization Problems

Consider the standard ℓ₁-minimization problem

$\underset{z}{\min }{\left\{\Vert z\Vert \right\}}_1:Az=b\},$

(2.1)

and the ℓ₁-minimization problem with non-negative constraints

$\underset{z}{\min }{\left\{\Vert z\Vert \right\}}_1:Az=b,z\ge 0\},$

(2.2)

where A ∈ ℝ^m×n(m < n) and b ∈ ℝ^m are given. We also consider the more general

$\underset{z}{\min }\left\{{\Vert z\Vert }_1:z\in P\right\},$

(2.3)

where P ⊆ ℝⁿ is a given polyhedral set. The solution of (2.1) is called the least ℓ₁-norm solution of the linear system Az = b. The solution of (2.2) is called the least ℓ₁-norm non-negative solution of the system Az = b, and the solution of (2.3) is referred to as the least ℓ₁-norm point in polyhedron P. Uniqueness of solutions to these problems plays a vital role in many aspects of sparse optimization ...