Compressed Sensing: SpaRSA and Image Registration using Random Projections

Mário Figueiredo, Robert D. Nowak and Stephen Wright the authors of GPSR are coming up with a faster method for reconstructing solutions from Compressed Sensing measurements. The algorithm is presented in this preprint: Sparse Reconstruction by Separable Approximation the abstract reads:

Finding sparse approximate solutions to large underdetermined linear systems of equations is a common problem in signal/image processing and statistics. Basis pursuit, the least absolute shrinkage and selection operator (LASSO), wavelet-based deconvolution and reconstruction, and compressed sensing (CS) are a few well-known areas in which problems of this type appear. One standard approach is to minimize an objective function that includes a quadratic (ℓ2) error term added to a sparsity-inducing (usually ℓ1) regularizer. We present an algorithmic framework for the more general problem of minimizing the sum of a smooth convex function and a nonsmooth, possibly nonconvex, sparsity-inducing function. We propose iterative methods in which each step is an optimization subproblem involving a separable quadratic term (diagonal Hessian) plus the original sparsity-inducing term. Our approach is suitable for cases in which this subproblem can be solved much more rapidly than the original problem. In addition to solving the standard ℓ2 − ℓ1 case, our approach handles other problems, e.g., ℓp regularizers with p less than 1, or group-separable (GS) regularizers. Experiments with CS problems show that our approach provides state-of-the-art speed for the standard ℓ2 − ℓ1 problem, and is also efficient on problems with GS regularizers

The algorithm seems to promise a faster capability than GPSR_BB. Let us note the potential use of non-convex terms in the regularization term. Thank you Jort.



Another paper caught my attention: Fast Global Image Registration Using Random Projections by Dennis Healy, Jr. and Gustavo Rohd. The abstract reads:

We describe a new method for efficiently computing the global optimum of least squares registration problems based on the recently developed theory of signal processing using random projections. The method is especially attractive for large scale registration problems where the goal is to register many images to a standard template. We test our new algorithm using real images of cells’ nuclei and show our method can outperform more traditional dimension reduction methods such as projections onto lower dimensional B-spline function spaces.

This is a very nice application where image registration uses the work of Mike Wakin and Richard Baraniuk on Random Projection of Smooth manifolds. Nice.

On a totally unrelated note, on Monday, the Monday Morning Algorithm series will feature the algorithm presented here.