CONVERGENCE OF THE LINEARIZED BREGMAN ITERATION FOR l1-NORM MINIMIZATION

One of the key steps in compressed sensing is to solve the basis pursuit problem min(u is an element of Rn){parallel to u parallel to(1) : Au = f}. Bregman iteration was very successfully used to solve this problem in [40]. Also, a simple and fast iterative algorithm based on linearized Bregman iteration was proposed in [40], which is described in detail with numerical simulations in [35]. A convergence analysis of the smoothed version of this algorithm was given in [11]. The purpose of this paper is to prove that the linearized Bregman iteration proposed in [40] for the basis pursuit problem indeed converges.