Authors
Wotao Yin (Rice), Stanley Osher (UCLA), Donald Goldfarb (Columbia), Jerome Darbon (UCLA)
Abstract
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 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
T 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.
Paper
- W. Yin, S. Osher, J. Darbon, and D. Goldfarb. Bregman Iterative Algorithms for Compressed Sensing and Related Problems [CAAM TR07-13]
Code
- 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.)