Iteratively Reweighted l1 Approaches to Sparse Composite Regularization

Motivated by the observation that a given signal x admits sparse representations in multiple dictionaries Psi(d) but with varying levels of sparsity across dictionaries, we propose two new algorithms for the reconstruction of (approximately) sparse signals from noisy linear measurements. Our first algorithm, Co-L1, extends the well- known lasso algorithm from the L1 regularizer parallel to Psi(x)parallel to 1 to composite regularizers of the form Sigma(d)lambda(d)parallel to Psi(d)x parallel to 1 while self-adjusting the regularization weights lambda(d). Our second algorithm, Co-IRW- L1, extends the well-known iteratively reweighted L1 algorithm to the same family of composite regularizers. We provide several interpretations of both algorithms: 1) majorization- minimization (MM) applied to a nonconvex log-sum-type penalty; 2) MM applied to an approximate l0- type penalty; 3) MMapplied to BayesianMAP inference under a particular hierarchical prior; and 4) variational expectation maximization (VEM) under a particular prior with deterministic unknown parameters. A detailed numerical study suggests that our proposed algorithms yield significantly improved recovery SNR when compared to their noncomposite L1 and IRW- L1 counterparts.