Tail-STELA for Fast Signal Recovery via Basis Pursuit

In this paper, noticing the accuracy enhancement of the tail minimization technique for basis pursuit, and the faster convergence speed of the Soft-Thresholding with Exact Line Search Algorithm (STELA), we propose the Tail-STELA that combines both methods to solve the sparse signal recovery problem via the basis pursuit. Moreover, we adopt the dual decomposition method that utilizes the augmented Lagrangian to reformulate the basis pursuit. In this way, the update in the primal domain is expressed as a LASSO problem and can be solved by LASSO solvers, e.g., the STELA. We call such an approach the Tail-DD-LASSO approach and propose the Tail-DD-STELA as an instance. Simulation results show that on the one hand, the Tail-DD-STELA and the Tail-DD-FISTA achieve the highest recovery rates for different sparsity levels. On the other hand, the Tail-STELA and the Tail-FISTA achieve almost the same recovery rate at a fraction of the computation time. More specifically, the proposed Tail-STELA has the fastest convergence speed.