ABSTRACT
In this chapter, we introduce a unified framework of the reweighted 1-algorithms for the 0-minimization problem
(P0) min x {‖x‖0 : x ∈ P},
where P ⊆ Rn 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= {x ∈ Rn : Ax = b}; (7.1) P is the set of non-negative solutions of an underdetermined system of
linear equations, i.e.,
P= {x ∈ Rn : Ax = b, x≥ 0}. (7.2)
Throughout this chapter, we assume b = 0 in (7.1) and (7.2). Numerical experiments indicate that the reweighted 1-algorithm is one of the most efficient algorithms for 0-minimization problems. To derive a reweighted 1-algorithm, we introduce the notion of merit function for sparsity. We then identify two large families of such functions, called M(1)- and M(2)-classes, which are used in both practical implementations and theoretical analysis of the reweighted 1-algorithms. The analysis in this chapter indicates that the reweighted 1algorithm can be developed systematically through the linearization of the merit function for sparsity. The convergence analysis for the reweighted 1-algorithm can be carried out under an assumption imposed on the range space of the transposed matrix and an appropriate choice of the merit function for sparsity. In
particular, some convergence results for the well-known Cande`s-Wakin-Boyd method in [53] and the p-quasinorm-based reweighted 1-method [107] can follow immediately from the generic results presented in this chapter.
