Fast IRLS for sparse reconstruction based on gaussian mixtures

The theory of compressed sensing has demonstrated that sparse signals can be reconstructed from few linear measurements. In this work, we propose a new class of iteratively reweighted least squares (IRLS) for sparse recovery. The proposed methods use a two state Gaussian scale mixture as a proxy for the signal model and can be interpreted as an Expectation Maximization algorithm that attempts to perform the constrained maximization of the log-likelihood function. Under some conditions, standard in the compressed sensing theory, the sequences generated by these algorithms converge to the fixed points of the maps that rule their dynamics. A condition for exact sparse recovery, that is verifible a posteriori, is derived and the convergence is proved to be quadratically fast in a neighborhood of the desired solution. Numerical experiments show that these new reconstructions schemes outperform classical IRLS for lp -minimization with p\in(0, 1] in terms of rate of convergence and accurac