SALSA and C-SALSA

(Constrained) Split Augmented Lagrangian Shrinkage Algorithm


Authors

Manya Afonso, Mário Figueiredo, José Bioucas-Dias,

Instituto de Telecomunicações, Instituto Superior Técnico,

Lisboa, PORTUGAL

Introduction

Several ill-posed imaging Linear Inverse Problems, such as image deblurring, denoising, reconstruction from projections, inpainting, some formulations of compressed sensing, can be treated as convex optimization problems, which involve minimizing a convex but possibly non-smooth regularization function, under the constraint that the solution explains the observations sufficiently well. One way to formulate the problem of estimating the unknown signal x, given the observation y, consists in a constrained optimization problem of the form

(C)

where Φ is the regularizer or regularization function, and ε >= 0. In the case where Φ(x) = ||x||_1, the above problem is usually known as basis pursuit denoising (BPD).

Most state-of-the-art methods for dealing with linear inverse problems, under convex, non-smooth regularizers (namely, Total Variation and L1), consider, rather than (C), the related unconstrained problem

(U)

where τ > 0 is the so-called regularization parameter.

Both formulations allow both wavelet-based (with orthogonal or frame-based representations) regularization or TV regularization.

The approach we propose for solving problems of the form (U) is based on a variable splitting to obtain an equivalent constrained optimization formulation, which is then addressed with an augmented Lagrangian method. The proposed algorithm is an instance of the so-called alternating direction method of multipliers (ADMM), for which convergence has been proved. Experiments on a set of image restoration and reconstruction benchmark problems show that the proposed algorithm is faster than the current state of the art methods. The speed of the proposed algorithm, which we term SALSA (split augmented Lagrangian shrinkage algorithm), comes from the fact that it uses (a regularized version of) the Hessian of the data fidelity term.

Our approach for solving optimization problems of the form (C) involves transforming the original constrained problem into an unconstrained one by adding the indicator function of the feasible set, the ellipsoid {x : ||Bx-y||<=ε}, to the objective in (C). The resulting unconstrained problem is then transformed into a different constrained problem, by the application of a variable splitting operation; finally, the obtained constrained problem is attacked with an augmented Lagrangian (AL) scheme, which is a variant of the ADMM. Since (as SALSA), the proposed method uses variable splitting and AL optimization, we call it C-SALSA (for constrained-SALSA).

Both algorithms require:

Experiments on a set of image restoration and reconstruction benchmark problems show that the proposed algorithm is faster than the current state of the art methods. A couple of examples are shown here.


Download Papers

SALSA

C-SALSA

Download Code

The MATLAB code for the latest version is available here.

Installation and usage instructions

See the file README.txt for installation instructions, and type "help salsa" or "help csalsa" at the MATLAB prompt.

Funding Acknowledgment

This work is supported by an EU Marie-Curie Fellowship (EST-SIGNAL program); contract MEST-CT-2005-021175.

Contact

In case of any queries or to report any problems with either the code or this webpage, please email Manya Afonso at:

<given name> (dot) <last name> (at) lx (dot) it (dot) pt


Last updated on January 13th 2012, by Manya Afonso.