Sparse Optimization Theory and Methods

Chapter 7

Reweighted ℓ₁-Algorithms

In this chapter, we introduce a unified framework of the reweighted ℓ₁-algorithms for the ℓ₀-minimization problem

$\begin{array}{cc}\left(P_0\right)& \underset{x}{\min }\left\{{\Vert x\Vert }_0:x\in P\right\}\end{array},$

where P ⊆ ℝⁿ is a polyhedral set. There are two important and special cases which have found wide applications in signal and image processing:

■  P is the solution set of an underdetermined system of linear equations, namely,

$P=\left\{x\in {ℝ}^n:Ax=b\right\};$

(7.1)

■  P is the set of non-negative solutions of an underdetermined system of linear equations, i.e.,

$P=\left\{x\in {ℝ}^n:Ax=b,x\ge 0\right\}.$

(7.2)

Throughout this chapter, we assume b ≠ 0 in (7.1) and (7.2). Numerical experiments indicate that the reweighted ℓ₁-algorithm is one of the most efficient algorithms for ℓ₀ -minimization problems. To ...