Bregman Iterative Algorithms for l1-Minimization with Applications to Compressed Sensing

We propose simple and extremely efficient methods for solving the basis pursuit problem min{parallel to u parallel to(1) : Au = f, u is an element of R-n}, 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 min(u is an element of Rn) mu parallel to u parallel to(1)+ 1/2 parallel to Au-f(k)parallel to(2)(2) for given matrix A and vector f(k). 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(inverted perpendicular) can be computed by fast transforms. Utilizing a fast fixed-point continuation solver that is based solely on such operations for solving the above unconstrained subproblem, we were able to quickly solve huge instances of compressed sensing problems on a standard PC.