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
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

Citations by Year