Compressed Sensing: Additional Solvers, SpaRSA, ProxIT and an unnamed solver.

I am adding five new solvers to the Compressed Sensing Big Picture page.

* SpaRSA : It is described in Sparse Reconstruction by Separable Approximation by Mário Figueiredo, Robert D. Nowak and Stephen Wright. Mario tells me that it will be up for evaluation at some point in time.

* ProxIT: It was mentioned earlier in Compressed sensing in astronomy by Jerome Bobin, Jean-Luc Starck, and Roland Ottensamer.

* A solver based on IT-LARS and StOMP in Sparse Representation-based Image Deconvolution by Iterative Thresholding by Jalal Fadili and Jean-Luc Starck. The abstract reads:

Image deconvolution algorithms with overcomplete sparse representations and fast iterative thresholding methods are presented. The image to be recovered is assumed to be sparsely represented in a redundant dictionary of transforms. These transforms are chosen to offer a wider range of generating atoms; allowing more flexibility in image representation and adaptativity to its morphological content. The deconvolution inverse problem is formulated as the minimization of an energy functional with a sparsity-promoting regularization (e.g. ℓ1 norm of the image representation coefficients). As opposed to quadratic programming solvers based on the interior point method, here, recent advances in fast solution algorithms of such problems, i.e. Stagewise Iterative Thresholding, are exploited to solve the optimization problem and provide fast and good image recovery results. Some theoretical aspects as well as computational and practical issues are investigated. Illustrations are provided for potential applicability of the method to astronomical data.

* I also just saw a presentation detailing the underlying mechanics of another category of solvers called Monotone Operator Splitting. An example of which is Image Deconvolution under Poisson Noise using Sparse Representations and Proximal Thresholding Iteration by Francois-Xavier Dupe , Jalal Fadili and Jean-Luc Starck.

Let us note that in the first paper, there is a smart use of translation operators not unlike the restriction operators used in geophysics (as featured in Sparco).

* This last algorithm does not have name but is presented in Fast Sparse Representation using Smoothed L0 Norm by G. Hosein Mohimani, Massoud Babaie-Zadeh and Christian Jutten. The abstract reads:

In this paper we present an algorithm for complex-valued sparse representation. In our previous work we presented an algorithm for Sparse representation based on smoothed l_0 norm. Here we extend that algorithm to complex-valued signals. The proposed algorithm is compared to FOCUSS algorithm and it is experimentally shown that the proposed algorithm is about two or three orders of magnitude faster than FOCUSS while providing approximately the same accuracy.

Credit: NASA/JPL/Space Science Institute, Cassini on approach to Enceladus.