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; TFOCS; SPGL1; TwIST; RecPF; glmnet; FPC_AS; UNLocBoX; ElemStatLearn; CoSaMP; Matlab; PROPACK; Yall1; CVX; L1TestPack; ParNes; TVAL3; FTVd; Mosek; na28
Cited in: 141 Documents
all top 5

Cited by 317 Authors

5 Lan, Guanghui
4 Cheng, Lizhi
4 Fountoulakis, Kimon
4 Gondzio, Jacek
4 Taylor, Jonathan E.
4 Villa, Silvia
3 Aybat, Necdet Serhat
3 Ouyang, Yuyuan
3 Peng, Jigen
3 Rosasco, Lorenzo A.
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 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 Aminifard, Zohre
1 Andersen, Martin S.
1 Aravkin, Aleksandr Y.
1 Arora, Raman
1 Ayvaci, Alper
1 Babaie-Kafaki, Saman
1 Bach, Francis R.
1 Bai, Yanqin
1 Baraniuk, Richard G.
1 Behboodi, Arash
1 Biau, Gérard
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, Tony Tony
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 Dassios, Ioannis K.
1 De Asmundis, Roberta
1 Degras, David A.
1 Dexter, Nick C.
1 di Serafino, Daniela
1 Ding, Liang
1 Donatelli, Marco
1 Dong, Bin
1 Dong, Zhaoyang
1 Doostan, Alireza
1 Eckstein, Jonathan
1 Eldred, Michael S.
1 Esmaeili, Hamid
1 Esser, Ernie
1 Faghihi, Reza
...and 217 more Authors
all top 5

Cited in 66 Serials

13 SIAM Journal on Imaging Sciences
10 The Annals of Statistics
9 Computational Optimization and Applications
7 Mathematical Programming. Series A. Series B
6 SIAM Journal on Optimization
5 Journal of Computational and Applied Mathematics
4 Inverse Problems
4 Journal of Scientific Computing
3 Information Sciences
3 Circuits, Systems, and Signal Processing
3 Numerical Algorithms
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 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 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 Computational Statistics and Data Analysis
1 International Journal of Computer Vision
1 Computational and Applied Mathematics
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

Citations by Year