Compressed Sensing: Solving the Basis Pursuit problem with a Bregman Iterative Algorithm

While TwIST is solving (IST) compressed sensing reconstruction problems with a two-step Iterative shrinkage/thresholding (IST) algorithm for different regularization terms. Wotao Yin, Stanley Osher, Donald Goldfarb and Jerome Darbon are using Bregman iterative regularization to attack this Basis Pursuit problem in Bregman Iterative Algorithms for Compressed Sensing and Related Problems. The abstract reads:

We propose simple and extremely efficient methods for solving the Basis Pursuit problem



which is used in compressed sensing. Our methods are based on Bregman iterative regularization and they give a very accurate solution after solving only a very small number of instances of the unconstrained problem



for given matrix A and vector fk. We show analytically that this iterative approach yields exact solutions in a finite number of steps, and present numerical results that demonstrate that as few as two to six iterations are sufficient in most cases. Our approach is especially useful for many compressed sensing applications where matrix-vector operations involving A and A' can be computed by fast transforms. Utilizing a fast fixed-point continuation solver that is solely based on such operations for solving the above unconstrained sub-problem, we were able to solve huge instances of compressed sensing problems quickly on a standard PC.

They also seem to aim for very large reconstruction problems as well. The webpage for this effort is here and the code is here. The main difference would certainly be in how much time is spent on both algorithms to solve the same problem but also the fact that the TwIST would have the advantage of also dealing with non-convex regularization lp terms with p =0.7 or 0.8. If anybody has done the comparison between the two methods with p=1, I'd love to hear about it.

Source: Rice Compressed Sensing page.