SPGL1 swMATH ID: 8365 Software Authors: van den Berg, Ewout; Friedlander, Michael P. Description: SPGL1: A solver for large-scale sparse reconstruction: Probing the Pareto frontier for basis pursuit solutions. The basis pursuit problem seeks a minimum one-norm solution of an underdetermined least-squares problem. Basis Pursuit DeNoise (BPDN) fits the least-squares problem only approximately, and a single parameter determines a curve that traces the optimal trade-off between the least-squares fit and the one-norm of the solution. We prove that this curve is convex and continuously differentiable over all points of interest, and show that it gives an explicit relationship to two other optimization problems closely related to BPDN. We describe a root-finding algorithm for finding arbitrary points on this curve; the algorithm is suitable for problems that are large scale and for those that are in the complex domain. At each iteration, a spectral gradient-projection method approximately minimizes a least-squares problem with an explicit one-norm constraint. Only matrix-vector operations are required. The primal-dual solution of this problem gives function and derivative information needed for the root-finding method. Numerical experiments on a comprehensive set of test problems demonstrate that the method scales well to large problems. Homepage: http://www.cs.ubc.ca/~mpf/spgl1/ Source Code: https://github.com/vegarant/spgl1 Dependencies: Matlab Keywords: basis pursuit; convex program; duality; root-finding; Newton’s method; projected gradient; one-norm regularization; sparse solutions Related Software: PDCO; NESTA; CoSaMP; FPC_AS; TwIST; CVX; UNLocBoX; Regularization tools; TFOCS; L1TestPack; GitHub; RecPF; ElemStatLearn; SparseLab; Matlab; L1-MAGIC; Mosek; PROPACK; UCI-ml; SeDuMi Cited in: 200 Publications Standard Articles 2 Publications describing the Software, including 2 Publications in zbMATH Year Sparse optimization with least-squares constraints. Zbl 1242.49061van den Berg, Ewout; Friedlander, Michael P. 2011 Probing the Pareto frontier for basis pursuit solutions. Zbl 1193.49033van den Berg, Ewout; Friedlander, Michael P. 2008 all top 5 Cited by 457 Authors 7 Doostan, Alireza 6 Adcock, Ben 5 Guo, Ling 5 Lu, Zhaosong 5 Ma, Shiqian 5 Narayan, Akil C. 5 Xiao, Yunhai 4 Aravkin, Aleksandr Y. 4 Friedlander, Michael P. 4 Goldfarb, Donald 4 Pong, Ting Kei 3 Ascher, Uri M. 3 Blanchard, Jeffrey D. 3 Chen, Xiaojun 3 Haber, Eldad 3 Hampton, Jerrad 3 Hansen, Anders C. 3 Huang, Hui 3 Li, Xinxin 3 Lin, Guang 3 Steidl, Gabriele 3 Tanner, Jared W. 3 van den Berg, Ewout 3 van Leeuwen, Tristan 3 Webster, Clayton G. 3 Wolkowicz, Henry 3 Wu, Soon-Yi 3 Yang, Xiu 3 Yuan, Xiaoming 3 Zhang, Wenxing 3 Zhu, Hong 2 Alemazkoor, Negin 2 Alexanderian, Alen 2 Baker, Nathan A. 2 Bala Abubakar, Auwal 2 Barlaud, Michel 2 Boyd, Nicholas 2 Boyd, Stephen Poythress 2 Burke, James V. 2 Cheng, Lizhi 2 Dexter, Nick C. 2 Ding, Liang 2 Dossal, Charles 2 Drusvyatskiy, Dmitriy 2 Fang, Shu-Cherng 2 Gelb, Anne 2 Herrmann, Felix J. 2 Iskandarani, Mohamed 2 Jakeman, John Davis 2 Jiang, Shan 2 Keshavarzzadeh, Vahid 2 Kirby, Robert M. II 2 Kumam, Poom 2 Kumar, Rajiv 2 Le Maître, Olivier P. 2 Lei, Huan 2 Li, Xudong 2 Liu, Yongle 2 Lorenz, Dirk Alfred 2 Loris, Ignace 2 Luiken, Nick 2 Meidani, Hadi 2 Ng, Michael Kwok-Po 2 Perez, Guillaume 2 Pfetsch, Marc E. 2 Recht, Benjamin 2 Shehu, Yekini 2 Sui, Yi 2 Sun, Defeng 2 Tenorio, Luis 2 Toh, Kim Chuan 2 Womersley, Robert S. 2 Yu, Peiran 2 Zhou, Tao 2 Zhu, Wei 1 Abrishami-Moghaddam, Hamid 1 Abusag, Nadia M. 1 Adam, Lukáš 1 Ambat, Sooraj K. 1 Ament, Sebastian 1 Ames, Brendan P. W. 1 Andersson, Fredrik K. 1 Andersson, Mats 1 Antoine, Philippe 1 Antun, Vegard 1 Awwal, Aliyu Muhammed 1 Aybat, Necdet Serhat 1 Babaie-Zadeh, Massoud 1 Bao, Anyi 1 Baraldi, Robert 1 Bastounis, Alexander 1 Batenburg, Kees Joost 1 Becker, Stephen R. 1 Behboodi, Arash 1 Beinert, Robert 1 Birgin, Ernesto G. 1 Bleichrodt, Folkert 1 Bogdan, Małgorzata 1 Bouwmans, Thierry 1 Brugiapaglia, Simone ...and 357 more Authors all top 5 Cited in 80 Serials 14 SIAM Journal on Optimization 13 Journal of Computational Physics 12 SIAM Journal on Scientific Computing 9 Mathematical Programming. Series A. Series B 7 Journal of Scientific Computing 7 SIAM Journal on Imaging Sciences 6 Computational Optimization and Applications 5 Numerical Algorithms 5 Journal of Mathematical Imaging and Vision 5 Applied and Computational Harmonic Analysis 5 Mathematical Programming Computation 4 Computer Methods in Applied Mechanics and Engineering 4 Inverse Problems 4 Journal of Computational and Applied Mathematics 4 Applied Numerical Mathematics 4 Computational Geosciences 4 Inverse Problems and Imaging 4 SIAM/ASA Journal on Uncertainty Quantification 3 Computers & Mathematics with Applications 3 Optimization Letters 2 Mathematics of Computation 2 Automatica 2 SIAM Journal on Numerical Analysis 2 Optimization 2 Multidimensional Systems and Signal Processing 2 Linear Algebra and its Applications 2 The Journal of Fourier Analysis and Applications 2 INFORMS Journal on Computing 2 Vietnam Journal of Mathematics 2 Optimization and Engineering 2 Foundations of Computational Mathematics 2 Journal of Machine Learning Research (JMLR) 2 Multiscale Modeling & Simulation 2 Information and Inference 2 East Asian Journal on Applied Mathematics 1 Artificial Intelligence 1 Theoretical and Computational Fluid Dynamics 1 ACM Transactions on Mathematical Software 1 Calcolo 1 Information Sciences 1 Journal of the American Statistical Association 1 Journal of Optimization Theory and Applications 1 Mathematics of Operations Research 1 Nonlinear Analysis. Theory, Methods & Applications. Series A: Theory and Methods 1 Circuits, Systems, and Signal Processing 1 Applied Mathematics and Mechanics. (English Edition) 1 Constructive Approximation 1 Signal Processing 1 Machine Learning 1 Journal of Global Optimization 1 Applied Mathematical Modelling 1 European Journal of Operational Research 1 International Journal of Computer Mathematics 1 Proceedings of the National Academy of Sciences of the United States of America 1 SIAM Journal on Applied Mathematics 1 SIAM Review 1 International Journal of Computer Vision 1 Computational and Applied Mathematics 1 Mathematical Problems in Engineering 1 Abstract and Applied Analysis 1 Optimization Methods & Software 1 Journal of Inequalities and Applications 1 PAA. Pattern Analysis and Applications 1 Sādhanā 1 Sampling Theory in Signal and Image Processing 1 Analysis and Applications (Singapore) 1 Journal of Computational Acoustics 1 Networks and Spatial Economics 1 European Series in Applied and Industrial Mathematics (ESAIM): Mathematical Modelling and Numerical Analysis 1 Communications in Computational Physics 1 Mathematical Modelling of Natural Phenomena 1 Set-Valued and Variational Analysis 1 Science China. Information Sciences 1 GEM - International Journal on Geomathematics 1 Communications in Mathematics and Statistics 1 Journal of the Operations Research Society of China 1 Computer Science Review 1 AMM. Applied Mathematics and Mechanics. (English Edition) 1 Results in Applied Mathematics 1 SIAM Journal on Mathematics of Data Science all top 5 Cited in 34 Fields 103 Numerical analysis (65-XX) 99 Operations research, mathematical programming (90-XX) 62 Information and communication theory, circuits (94-XX) 22 Statistics (62-XX) 21 Calculus of variations and optimal control; optimization (49-XX) 20 Computer science (68-XX) 12 Probability theory and stochastic processes (60-XX) 11 Harmonic analysis on Euclidean spaces (42-XX) 10 Approximations and expansions (41-XX) 9 Partial differential equations (35-XX) 8 Linear and multilinear algebra; matrix theory (15-XX) 6 Geophysics (86-XX) 5 Systems theory; control (93-XX) 4 Operator theory (47-XX) 4 Fluid mechanics (76-XX) 3 Functional analysis (46-XX) 3 Convex and discrete geometry (52-XX) 3 Biology and other natural sciences (92-XX) 2 Dynamical systems and ergodic theory (37-XX) 1 Mathematical logic and foundations (03-XX) 1 Combinatorics (05-XX) 1 Number theory (11-XX) 1 Special functions (33-XX) 1 Ordinary differential equations (34-XX) 1 Integral transforms, operational calculus (44-XX) 1 Differential geometry (53-XX) 1 Global analysis, analysis on manifolds (58-XX) 1 Mechanics of particles and systems (70-XX) 1 Mechanics of deformable solids (74-XX) 1 Optics, electromagnetic theory (78-XX) 1 Classical thermodynamics, heat transfer (80-XX) 1 Statistical mechanics, structure of matter (82-XX) 1 Astronomy and astrophysics (85-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX) Citations by Year