Rice University, L1-Related Optimization Project

::News      ::Courses      ::People      ::Papers and Reports      ::Software

Bregman Iterative Algorithms for Constrained Compressed Sensing and Related Problems


Wotao Yin (Rice), Stanley Osher (UCLA), Donald Goldfarb (Columbia), Jerome Darbon (UCLA)


We propose simple and very 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 AT 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.


  • W. Yin, S. Osher, J. Darbon, and D. Goldfarb. Bregman Iterative Algorithms for Compressed Sensing and Related Problems [CAAM TR07-13]


  • The Bregman solver will be upgraded to Version 2.0. A currently better (in terms of speed and robustness) solver is FPC_AS [link].
    Version 1.0, October 18, 2007. [Download here]
    (Note: this package includes a few files from a published version of the code FPC [link]. Update these files to the latest versions may speed up the code.)