Abstract. We propose simple and extremely efficient methods for solving the basis pursuit problem min{ u 1 : Au = f, u ∈ 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∈R n μ u 1 + 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 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.
Yin et al. REF have described a method for solving the basis pursuit problem, i.e., (4) with , where the main computational cost is the solution of a small number of problems of the form (2), for different values of and possibly also .
Bregman iterative algorithms for ℓ1-minimization with applications to compressed sensing
SIAM J. Imaging Sci
Mathematics Computer Science