Convergence of the linearized Bregman iteration for ℓ₁-norm minimization

One of the key steps in compressed sensing is to solve the basis pursuit problem <!-- MATH $\min_{u\in\mathbb{R}^n}\{\|u\|_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.