Becker, Stephen; Bobin, Jérôme; Candès, Emmanuel J. NESTA: A fast and accurate first-order method for sparse recovery. (English) Zbl 1209.90265 SIAM J. Imaging Sci. 4, No. 1, 1-39 (2011). Summary: Accurate signal recovery or image reconstruction from indirect and possibly undersampled data is a topic of considerable interest; for example, the literature in the recent field of compressed sensing is already quite immense. This paper applies a smoothing technique and an accelerated first-order algorithm, both from Yu. Nesterov [Math. Program. 103, No. 1 (A), 127–152 (2005; Zbl 1079.90102)], and demonstrates that this approach is ideally suited for solving large-scale compressed sensing reconstruction problems as (1) it is computationally efficient; (2) it is accurate and returns solutions with several correct digits; (3) it is flexible and amenable to many kinds of reconstruction problems; and (4) it is robust in the sense that its excellent performance across a wide range of problems does not depend on the fine tuning of several parameters. Comprehensive numerical experiments on realistic signals exhibiting a large dynamic range show that this algorithm compares favorably with recently proposed state-of-the-art methods. We also apply the algorithm to solve other problems for which there are fewer alternatives, such as total-variation minimization and convex programs seeking to minimize the \(\ell_1\) norm of \(W_x\) under constraints, in which \(W\) is not diagonal. The code is available online as a free package in the Matlab language. Cited in 131 Documents MSC: 90C06 Large-scale problems in mathematical programming 90C25 Convex programming 94A08 Image processing (compression, reconstruction, etc.) in information and communication theory Keywords:Nesterov’s method; smooth approximations of nonsmooth functions; \(\ell_1\) minimization; duality in convex optimization; continuation methods; compressed sensing; total-variation minimization Citations:Zbl 1079.90102 Software:NESTA; CoSaMP; PDCO; Matlab; glmnet; RecPF; na28; FPC_AS PDFBibTeX XMLCite \textit{S. Becker} et al., SIAM J. Imaging Sci. 4, No. 1, 1--39 (2011; Zbl 1209.90265) Full Text: DOI arXiv Link