ParNes swMATH ID: 8366 Software Authors: Gu, Ming; Lim, Lek-Heng; Wu, Cinna Julie Description: ParNes: A rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals 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‘es, we rely on Nesterov’s accelerated proximal gradient method, which takes \(O(sqrt {1/varepsilon })\) iterations to come within \(varepsilon > 0\) 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. Homepage: http://link.springer.com/article/10.1007%2Fs11075-012-9668-5 Keywords: basis pursuit; Newton’s method; Pareto curve; Nesterov’s method; compressed sensing; convex minimization; duality; lasso Related Software: TFOCS; PDCO; FPC_AS; SPGL1; NESTA; RecPF; L1TestPack; PROPACK; condat_tv; NETLIB LP Test Set; PNOPT; FPC; SpaRSA; TwIST; IMRO; l1_ls; UNLocBoX; LBFGS-B; NNLS; OSGA Cited in: 12 Documents all top 5 Cited by 23 Authors 2 Candès, Emmanuel J. 2 Cheng, Lizhi 2 Xiao, Lin 1 Alli-Oke, Razak O. 1 Becker, Stephen R. 1 Derksen, Harm 1 Fadili, Jalal M. 1 Grant, Michael C. 1 Gu, Ming 1 Heath, William Paul 1 Karimi, Sahar 1 Liang, Jingwei 1 Lim, Lek-Heng 1 Lin, Qihang 1 Neumaier, Arnold 1 O’Donoghue, Brendan 1 Peyré, Gabriel 1 Shu, Shi 1 Vavasis, Stephen A. 1 Wu, Cinna Julie 1 Zhang, Hui 1 Zhang, Tong 1 Zhu, Wei all top 5 Cited in 10 Serials 3 SIAM Journal on Optimization 1 Journal of Computational and Applied Mathematics 1 Numerical Algorithms 1 Mathematical Programming. Series A. Series B 1 Computational Optimization and Applications 1 Foundations of Computational Mathematics 1 Optimization Letters 1 Advances in Applied Mathematics and Mechanics 1 Mathematical Programming Computation 1 SIAM Journal on Applied Algebra and Geometry all top 5 Cited in 7 Fields 11 Operations research, mathematical programming (90-XX) 7 Numerical analysis (65-XX) 3 Calculus of variations and optimal control; optimization (49-XX) 2 Linear and multilinear algebra; matrix theory (15-XX) 2 Computer science (68-XX) 2 Information and communication theory, circuits (94-XX) 1 Statistics (62-XX) Citations by Year