CS: The Split Bregman Method for Compressed Sensing and attendant code.

At the L1 meeting at Texas A&M, Tom Goldstein and I briefly talked about the need for the algorithm folks to share their codes with the rest of the Compressed Sensing community. This is in part due to the need for other areas of Compressed Sensing to integrate their algorithm directly in their eventual physical compression / measurement scheme.

At the meeting, Tom and Stan Osher gave these two talks :

1. Fast Bregman Iteration for Compressive Sensing and Sparse Denoising
2. The split Bregman method for L1-regularized problems

Now they are releasing a report and the attendant code in The Split Bregman Method for L1 Regularized Problems by Tom Goldstein and Stan Osher. The abstract reads:

The class of L1-regularized optimization problems has received much attention recently because of the introduction of “compressed sensing,” which allows images and signals to be reconstructed from small amounts of data. Despite this recent attention, many L1-regularized problems still remain difficult to solve, or require techniques that are very problem-specific. In this paper, we show that Bregman iteration can be used to solve a wide variety of constrained optimization problems. Using this technique, we propose a “Split Bregman” method, which can solve a very broad class of L1-regularized problems. We apply this technique to the ROF functional for image denoising, and to a compressed sensing problem that arises in Magnetic Resonance Imaging.

The introduction gives a good overview on the difference with the FPC solver. The associated code is here. As far as I can tell this is the second algorithm based on the Bregman method that is publicly available. While the previous instance was solving :

this new algorithm is solving for the more general:

with E a non-differentiable function. [Update August 19, 2008: Stan Osher rightly steers my attention to the fact that E(u) needs to be the sum of L1 norms of certain items for this to be a good algorithm, e.g., TV(u), L1 sum of wavelet coefficients, etc...]


As opposed to other codes, this one is written in C++ but as Tom points out in the readme section:

These codes have only been tested on an SUSE UNIX platform, using the g++ compiler. However, these codes do not use any non-standard libraries or syntax, and should be fairly easy to build/use on other platforms.

I am sure that at some point we will see mex file version of it so that it can be readily used with Matlab.