Linearized Bregman iterations for compressed sensing
Finding a solution of a linear equation A u = f Au=f 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 ℓ 1 \ell _1 norm solution is needed. This means that the algorithm should be tailored for large scale and completely dense matrices A A , while A u Au and A T u A^Tu 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 ℓ 1 \ell _1 norm solution of A u = f Au=f as shown by numerical simulations. Hence, it can be used as another choice of an efficient tool in compressed sensing.