A new accelerated alternating minimization method for analysis sparse recovery

This paper proposes a new method based on accelerated alternating minimization (AAM) for analysis sparse recovery. This method is extremely attractive as (1) it is very simple and computationally efficient, (2) it exhibits a fast convergence rate, (3) it is flexible and amenable to many kinds of reconstruction problems. We establish the connection between the classical alternating minimization (AM) method and the well-known proximal gradient (PG) method. Thus combining the accelerated proximal gradient (APG) method with the Moreau proximal smoothing technique, a new smoothing-based AAM (SAAM) method, which can obtain an ϵ-optimal solution within O(1/ϵ) iterations, is designed. Numerical experiments on randomly generated data and real image reconstruction show that this method compares favorably with several state-of-the-art methods.