Quadratically fast IRLS for sparse signal recovery

Abstract

We present a new class of iterative algorithms for sparse recovery problems that combine iterative support detection and estimation.

More precisely, these methods use a two state Gaussian scale mixture as a proxy for the signal model and can be interpreted both as iteratively reweighted least squares (IRLS) and Expectation/Maximization (EM) algorithms for the constrained maximization of the log-likelihood function. Under certain conditions, these methods are proved to converge to a sparse solution and to be quadratically fast in a neighborhood of that sparse solution, outperforming classical IRLS for ℓ_τ-minimization. Numerical experiments validate the theoretical derivations and show that these new reconstruction schemes outperform classical IRLS for ℓ_τ-minimization with τ ∈ (0, 1] in sparsity-undersampling tradeoff.