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

Abstract

One of the key steps in compressed sensing is to solve the basis pursuit problem min urnu1: 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. © 2009 American Mathematical Society.