Nesterov's algorithm solving dual formulation for compressed sensing Dedicated to Professor Benyu Guo on the occasion of his seventieth birthday with friendship and esteem

We develop efficient algorithms for solving the compressed sensing problem. We modify the standard ^ℓ1 regularization model for compressed sensing by adding a quadratic term to its objective function so that the objective function of the dual formulation of the modified model is Lipschitz continuous. In this way, we can apply the well-known Nesterov algorithm to solve the dual formulation and the resulting algorithms have a quadratic convergence. Numerical results presented in this paper show that the proposed algorithms outperform significantly the state-of-the-art algorithm NESTA in accuracy.