Feishe Chen (current student), Lixin Shen, Bruce W. Suter, and Yuesheng Xu
Abstract: An accurate and efficient algorithm for an l1-norm minimization problem is highly needed and is crucial for the success of sparse signal recovery in compressive sampling, a recent development in the field of data analysis. Most of existing algorithms in the literature give an approximated solution to the problem. We tackle the ℓ1-norm minimization problem by equivalently reformulating it via an indicator function which describes the constraints for the problem. It turns out that the resulting model can be solved efficiently and accurately by using an elegant proximity operator based algorithm. We establish the 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.
UCLA Computational and Applied Mathematics Reports (12-63)