In this article we propose an algorithm, NESTA-LASSO, for the LASSO problem (i.e., an underdetermined linear least-squares problem with a one-norm constraint on the solution) that exhibits linear convergence under the restricted isometry property (RIP) and some other reasonable assumptions. Inspired by the state-of-the-art sparse recovery method, NESTA, we rely on an accelerated proximal gradient method proposed by Nesterov in 1983 that takes O(e^(-1/2)) iterations to come within e > 0 of the optimal value. We introduce a modification to Nesterov's method that regularly updates the prox-center in a provably optimal manner, resulting in the linear convergence of NESTA-LASSO under reasonable assumptions. Our work is motivated by recent advances in solving the basis pursuit denoising (BPDN) problem (i.e., approximating the minimum one-norm solution to an underdetermined least squares problem). Thus, one of our goals is to show that NESTA-LASSO can be used to solve the BPDN problem. We use NESTA-LASSO to solve a subproblem within the Pareto root-finding method used by the state-of-the-art BPDN solver SPGL1. The resulting algorithm is called PARNES, and we show, experimentally, that it is comparable to currently available solvers.
Citation
UC Berkeley preprint