Bregman Iterative Algorithms for \ell1-Minimization with Applications to Compressed Sensing

Wotao Yin, Stanley J. Osher, Donald Goldfarb, Jérôme DarbonSIAM J. Imaging Sci 2008 · DOI · OpenReview

Abstract

We propose simple and extremely efficient methods for solving the basis pursuit problem $\min\{\|u\|_1 : Au = f, u\in\mathbb{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\in\mathbb{R}^n} \mu\|u\|_1+\frac{1}{2}\|Au-f^k\|_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^\top$ 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.
BibTeX
@article{yin2008bregman,
  author = {Wotao Yin and Stanley J. Osher and Donald Goldfarb and Jérôme Darbon},
  title = {{Bregman Iterative Algorithms for \textbackslash\{\}ell1-Minimization with Applications to Compressed Sensing}},
  journal = {SIAM J. Imaging Sci.},
  year = {2008},
  doi = {10.1137/070703983},
}

Loading related content...

Figure