Fast and Accurate Algorithm for l1 Minimization Problems in Compressive Sampling (Preprint)

摘要

An accurate and efficient algorithm for solving the constrained 1- norm minimization problem is highly needed and is crucial for the success of sparse signal recovery in compressive sampling. Most of existing algorithms in the literature give an approximate solution to the problem. We tackle the constrained 1-norm minimization problem by reformulating it via an indicator function which describes the constraints. The resulting model is solved efficiently and accurately by using an elegant proximity operator based algorithm. We establish convergence analysis of the resulting algorithm. Numerical experiments show that the proposed algorithm performs well for sparse signals with magnitudes over a high dynamic range. Furthermore, it performs significantly better than the well-known algorithm NESTA in terms of the quality of restored signals and the computational complexity measured in the CPU-time consumed.