NESTA swMATH ID: 6576 Software Authors: Becker, Stephen; Bobin, Jerome; Candes, Emmanuel J. Description: NESTA: A fast and accurate first-order method for sparse recovery. 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 {it 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. Homepage: http://epubs.siam.org/doi/pdf/10.1137/090756855 Dependencies: Matlab Keywords: Nesterov’s method; smooth approximations of nonsmooth functions; \(ell_1\) minimization; duality in convex optimization; continuation methods; compressed sensing; total-variation minimization Related Software: PDCO; SPGL1; TFOCS; TwIST; RecPF; glmnet; UNLocBoX; FPC_AS; CoSaMP; ElemStatLearn; Yall1; Matlab; PROPACK; TVAL3; ParNes; UCI-ml; CVX; LIBSVM; L1TestPack; CUTEr Cited in: 152 Documents Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year NESTA: A fast and accurate first-order method for sparse recovery. Zbl 1209.90265Becker, Stephen; Bobin, Jérôme; Candès, Emmanuel J. 2011 all top 5 Cited by 341 Authors 5 Lan, Guanghui 5 Villa, Silvia 4 Cheng, Lizhi 4 Fountoulakis, Kimon 4 Gondzio, Jacek 4 He, Xing 4 Rosasco, Lorenzo A. 4 Taylor, Jonathan E. 3 Aminifard, Zohre 3 Aybat, Necdet Serhat 3 Babaie-Kafaki, Saman 3 Iyengar, Garud N. 3 Ouyang, Yuyuan 3 Peng, Jigen 3 Tibshirani, Ryan J. 3 Wu, Soon-Yi 3 Xiao, Yunhai 3 Yin, Wotao 3 Yu, Yongchao 3 Zhang, Yin 2 Adcock, Ben 2 Becker, Stephen R. 2 Boyd, Stephen Poythress 2 Candès, Emmanuel J. 2 Chen, Feishe 2 Chen, Jein-Shan 2 Chen, Yunmei 2 Fadili, Jalal M. 2 Hansen, Per Christian 2 Huang, Ting-Zhu 2 Landi, Germana 2 Lockhart, Richard A. 2 Murtagh, Fionn D. 2 Osher, Stanley Joel 2 Shen, Chungen 2 Shen, Lixin 2 Shu, Shi 2 Starck, Jean-Luc 2 Sun, Defeng 2 Suter, Bruce W. 2 Teboulle, Marc 2 Tibshirani, Robert John 2 Tillmann, Andreas M. 2 Toh, Kim Chuan 2 Wen, Bo 2 Wen, Zaiwen 2 Wu, Caiying 2 Xu, Yuesheng 2 Yuan, Xiaoming 2 Zhang, Lei-Hong 2 Zhang, Xiaoqun 2 Zhu, Hong 2 Zhu, Wei 1 Agarwal, Alekh 1 Alcantara, Jan Harold 1 Andersen, Martin S. 1 Aravkin, Aleksandr Y. 1 Arora, Raman 1 Ayvaci, Alper 1 Bach, Francis R. 1 Bai, Yanqin 1 Baraniuk, Richard G. 1 Behboodi, Arash 1 Biau, Gérard 1 Bienstock, Daniel 1 Bobin, Jérôme 1 Bolte, Jérôme 1 Borgnat, Pierre 1 Brown, Lawrence David 1 Buccini, Alessandro 1 Bühlmann, Peter 1 Buja, Andreas 1 Burger, Martin 1 Cadre, Benoît 1 Cai, Tianwen 1 Cao, Yongxiu 1 Caramanis, Constantine 1 Chai, Yi 1 Chan, Tony Fan-Cheong 1 Chen, Dai-Qiang 1 Chen, Guo 1 Chen, Jianli 1 Chen, Tao 1 Chen, Xiaojun 1 Chen, Ziang 1 Colbrook, Matthew J. 1 Cui, Angang 1 Cui, Yan 1 Dai, Xiangguang 1 Dargahi, Fatemeh 1 Dassios, Ioannis K. 1 De Asmundis, Roberta 1 Degras, David A. 1 Deng, Weiwei 1 Dexter, Nick C. 1 di Serafino, Daniela 1 Ding, Liang 1 Donatelli, Marco 1 Dong, Bin 1 Dong, Zhaoyang ...and 241 more Authors all top 5 Cited in 69 Serials 14 SIAM Journal on Imaging Sciences 11 Computational Optimization and Applications 10 The Annals of Statistics 7 Mathematical Programming. Series A. Series B 6 SIAM Journal on Optimization 5 Journal of Computational and Applied Mathematics 4 Inverse Problems 4 Circuits, Systems, and Signal Processing 4 Journal of Scientific Computing 4 Numerical Algorithms 3 Information Sciences 3 Neural Networks 3 SIAM Journal on Scientific Computing 3 Journal of Machine Learning Research (JMLR) 2 Journal of Computational Physics 2 Machine Learning 2 Journal of Mathematical Imaging and Vision 2 Applied and Computational Harmonic Analysis 2 Computational and Applied Mathematics 2 Journal of Industrial and Management Optimization 2 Optimization Letters 2 Inverse Problems and Imaging 2 Mathematical Programming Computation 2 Science China. Mathematics 2 Science China. Information Sciences 2 Statistics and Computing 1 Computers & Mathematics with Applications 1 Computer Methods in Applied Mechanics and Engineering 1 Journal of the Franklin Institute 1 Mathematics of Computation 1 Theoretical and Computational Fluid Dynamics 1 ACM Transactions on Mathematical Software 1 BIT 1 Calcolo 1 Journal of Optimization Theory and Applications 1 Mathematics of Operations Research 1 SIAM Journal on Numerical Analysis 1 Applied Mathematics and Mechanics. (English Edition) 1 Journal of Computational Mathematics 1 Applied Numerical Mathematics 1 Optimization 1 Statistical Science 1 Journal of Global Optimization 1 Applied Mathematical Modelling 1 International Journal of Computer Mathematics 1 SIAM Review 1 Computational Statistics and Data Analysis 1 International Journal of Computer Vision 1 Journal of Inverse and Ill-Posed Problems 1 Journal of Convex Analysis 1 Advances in Computational Mathematics 1 Bernoulli 1 Abstract and Applied Analysis 1 Soft Computing 1 Acta Mathematica Sinica. English Series 1 Optimization and Engineering 1 Journal of Applied Mathematics and Computing 1 Multiscale Modeling & Simulation 1 Analysis and Applications (Singapore) 1 Mediterranean Journal of Mathematics 1 Journal of Shanghai Jiaotong University (Science) 1 Advances in Data Analysis and Classification. ADAC 1 Foundations and Trends in Machine Learning 1 Advances in Applied Mathematics and Mechanics 1 Frontiers of Computer Science 1 Communications in Mathematics and Statistics 1 Journal of the Operations Research Society of China 1 Journal of Mathematics 1 Sampling Theory, Signal Processing, and Data Analysis all top 5 Cited in 21 Fields 96 Operations research, mathematical programming (90-XX) 71 Numerical analysis (65-XX) 49 Information and communication theory, circuits (94-XX) 28 Statistics (62-XX) 23 Calculus of variations and optimal control; optimization (49-XX) 19 Computer science (68-XX) 3 Linear and multilinear algebra; matrix theory (15-XX) 3 Partial differential equations (35-XX) 2 Combinatorics (05-XX) 2 Harmonic analysis on Euclidean spaces (42-XX) 2 Operator theory (47-XX) 2 Probability theory and stochastic processes (60-XX) 2 Biology and other natural sciences (92-XX) 2 Systems theory; control (93-XX) 1 History and biography (01-XX) 1 Dynamical systems and ergodic theory (37-XX) 1 Approximations and expansions (41-XX) 1 Integral transforms, operational calculus (44-XX) 1 Convex and discrete geometry (52-XX) 1 Mechanics of deformable solids (74-XX) 1 Fluid mechanics (76-XX) Citations by Year