We propose a first-order smoothed penalty algorithm (SPA) to solve the sparse recovery problem min{||x||_1 : Ax=b}. SPA is efficient as long as the matrix-vector product Ax and A^Ty can be computed efficiently; in particular, A need not be an orthogonal projection matrix. SPA converges to the target signal by solving a sequence of penalized optimization sub-problems, and each sub-problem is solved using Nesterov’s optimal algorithm for simple sets [13, 14]. We show that the SPA iterates x_k are eps-feasible, i.e. ||Ax_k-b||_2<= eps and eps-optimal, i.e. | ||x_k||_1-||x*||_1 | <= eps after O(eps^(-3/2)) iterations. We also bound the sub-optimality, | ||x_k||_1-||x*||_1 | for any iterate x_k; thus, the user can stop the algorithm at any iteration k with guarantee on the sub-optimality. SPA is able to work with L_1, L_2 or L_infinity penalty on the infeasibility, and SPA can be easily extended to solve the relaxed recovery problem min{||x||_1 : ||Ax-b||_2}.
Citation
IEOR Department, Columbia University, April 2009