Compressed Sensing: Greedier and Faster for Linear and Nonlinear Sparse Inverse Problems, A new version of Sparsify.

Thomas Blumensath and Mike Davies just released three papers on greedy reconstructions algorithms (some of them are implemented in the Sparsify package) where the emphasis is in solving for large problems. The second paper also touches on an interesting development where the system to be solved is a nonlinear one while knowing the solution to be sparse. This is new and interesting in light of the manifold approach to compressed sensing. Obviously, this also means that Sparsify has just been updated and includes the greedy gradient algorithm for non-linear sparse inverse problems,

The first article is Fast greedy algorithms for large sparse inverse problems and the abstract reads:

In this paper we introduce and study algorithms to solve large linear equations, in which the solution is assumed to be sparse. We concentrate on greedy strategies and in particular study extensions to the recently introduced Gradient Pursuit framework. Different approaches are compared that select several elements per iteration, thereby significantly decreasing the computational complexity of the method. We argue in particular for the use of a so called stagewise weak selection strategy. Experiments with a range of sparse inverse problems show that a Gradient Pursuit algorithm with such a selection strategy is competitive to and in many cases outperforms other fast algorithms, both in terms of estimation accuracy and in terms of computation speed.

The second article is Gradient Pursuit for Non-Linear Sparse Signal Modelling, the abstract reads:

In this paper the linear sparse signal model is extended to allow more general, non-linear relationships and more general measures of approximation error. A greedy gradient based strategy is presented to estimate the sparse coefficients. This algorithm can be understood as a generalisation of the recently introduced Gradient Pursuit framework. Using the presented approach with the traditional linear model but with a different cost function is shown to outperform OMP in terms of recovery of the original sparse coefficients. A second set of experiments then shows that for the nonlinear model studied and for highly sparse signals, recovery is still possible in at least a percentage of cases.

Finally the third paper is entitled Faster & Greedier: algorithms for sparse reconstruction of large datasets and the abstract reads:

We consider the problem of performing sparse reconstruction of large-scale data sets, such as the image sequences acquired in dynamic MRI. Here, both conventional L1 minimization through interior point methods and Orthogonal Matching Pursuit (OMP) are not practical. Instead we present an algorithm that combines fast directional updates based around conjugate gradients with an iterative thresholding step similar to that in StOMP but based upon a weak greedy selection criterion. The algorithm can achieve OMP-like performance and the rapid convergence of StOMP but with MP-like complexity per iteration. We also discuss recovery conditions applicable to this algorithm.