ParNes: a rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals

By Ming Gu, Lek-Heng Lim, Cinna Julie Wu. 2009

30 citations recorded by the source corpus.

In this article, we propose an algorithm, nesta-lasso, for the lasso problem, i.e., an underdetermined linear least-squares problem with a 1-norm constraint on the solution. We prove under the assumption of the restricted isometry property (rip) and a sparsity condition on the solution, that nesta-lasso is guaranteed to be almost always locally linearly convergent. As in the case of the algorithm nesta, proposed by Becker, Bobin, and Candès, we rely on Nesterov’s accelerated proximal gradient method, which takes \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(\sqrt {1/\varepsilon })$\end{document} iterations to come within \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\varepsilon > 0$\end{document} of the optimal value. We introduce a modification to Nesterov’s method that regularly updates the prox-center in a provably optimal manner. The aforementioned linear convergence is in part due to this modification. In the second part of this article, we attempt to solve the basis pursuit denoising (bpdn) problem (i.e., approximating the minimum 1-norm solution to an underdetermined least squares problem) by using nesta-lasso in conjunction with the Pareto root-finding method employed by van den Berg and Friedlander in their spgl1 solver. The resulting algorithm is called parnes. We provide numerical evidence to show that it is comparable to currently available solvers.

Subfields: Biomedical Engineering, Computational Mechanics, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Biomedical Engineering

In Computational Mechanics

In Computer Vision and Pattern Recognition

Citations in the corpus

Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition (2016, background): “For example, Gu et al. [2013] prove that their al-gorithm achieves a linear convergence rate if A satisﬁes a restricted isometry property (RIP) and the solution is suﬃciently sparse.”
Templates for convex cone problems with applications to sparse signal recovery (2010, methodology): “For this value of mf (and with Lf = 1), the optimal restart number Kopt from [34] is about 80, which is consistent with the plot.”
Adaptive Restart for Accelerated Gradient Schemes (2012, unknown): “For strongly convex functions an alternative to choosing the optimal value of q in Algorithm 1 is to use restarting, [3, 11, 15, 16, 20].”
A Proximal-Gradient Homotopy Method for the Sparse Least-Squares Problem (2012, background): “Nesterov gave some suggestions along this direction in [32], and strategies such as periodic restart have been studied recently [21, 3].”