Iteratively Reweighted <named-content content-type="math" xlink:type="simple"><inline-formula><tex-math notation="LaTeX">$\ell_1$</tex-math></inline-formula> </named-content> Approaches to Sparse Composite Regularization

Abstract

Motivated by the observation that a given signal x admits sparse representations in multiple dictionaries Ψ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</sub> 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 ∥Ψx∥ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> to composite regularizers of the form Σ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</sub> λ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</sub> ∥Ψ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</sub> x <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> while self-adjusting the regularization weights λ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 Bo-type penalty; 3) MM applied to Bayesian MAP 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.