Linearized Bregman iterations for compressed sensing

Abstract

Finding a solution of a linear equation with various minimization properties arises from many applications. One such application is compressed sensing, where an efficient and robust-to-noise algorithm to find a minimal norm solution is needed. This means that the algorithm should be tailored for large scale and completely dense matrices , while and can be computed by fast transforms and the solution we seek is sparse. Recently, a simple and fast algorithm based on linearized Bregman iteration was proposed in [28, 32] for this purpose. This paper is to analyze the convergence of linearized Bregman iterations and the minimization properties of their limit. Based on our analysis here, we derive also a new algorithm that is proven to be convergent with a rate. Furthermore, the new algorithm is simple and fast in approximating a minimal norm solution of as shown by numerical simulations. Hence, it can be used as another choice of an efficient tool in compressed sensing.