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; TFOCS; GitHub; Regularization tools; UCI-ml; RecPF; L1TestPack; Mosek; Matlab; ElemStatLearn; SparseLab; L1-MAGIC; Yall1; PROPACK
Cited in: 219 Documents
all top 5

Cited by 504 Authors

8 Doostan, Alireza
7 Adcock, Ben
6 Pong, Ting Kei
5 Chen, Xiaojun
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 Yang, Xiu
3 Ascher, Uri M.
3 Blanchard, Jeffrey D.
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 Yuan, Xiaoming
3 Zhang, Wenxing
3 Zhu, Hong
2 Alemazkoor, Negin
2 Alexanderian, Alen
2 Antoine, Philippe
2 Baker, Nathan A.
2 Bala Abubakar, Auwal
2 Baraldi, Robert J.
2 Barlaud, Michel
2 Boyd, Nicholas
2 Boyd, Stephen Poythress
2 Brugiapaglia, Simone
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 Jacques, Laurent
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 Mathar, Rudolf
2 Meidani, Hadi
2 Ng, Michael Kwok-Po
2 Pan, Lili
2 Perez, Guillaume
2 Pfetsch, Marc E.
2 Recht, Benjamin
2 Schaeffer, Hayden
2 Shehu, Yekini
2 Shen, Chungen
2 Sui, Yi
2 Sun, Defeng
2 Tenorio, Luis
2 Toh, Kim Chuan
2 Tran, Giang N.
2 Tran, Hoang Anh
2 Ward, Rachel A.
2 Womersley, Robert S.
2 Yu, Peiran
2 Zhang, Lei-Hong
2 Zhou, Tao
1 Abrishami-Moghaddam, Hamid
1 Abusag, Nadia M.
1 Adam, Lukáš
1 Akian, Jean-Luc
1 Ambat, Sooraj K.
1 Ament, Sebastian
1 Ames, Brendan P. W.
1 Andersson, Fredrik K.
1 Andersson, Mats
1 Antun, Vegard
1 Awwal, Aliyu Muhammed
1 Aybat, Necdet Serhat
1 Babaie-Zadeh, Massoud
1 Bangun, Arya
...and 404 more Authors
all top 5

Cited in 84 Serials

14 Journal of Computational Physics
14 SIAM Journal on Optimization
12 SIAM Journal on Scientific Computing
10 Mathematical Programming. Series A. Series B
9 SIAM Journal on Imaging Sciences
8 Computational Optimization and Applications
7 Journal of Scientific Computing
6 Applied and Computational Harmonic Analysis
5 Computer Methods in Applied Mechanics and Engineering
5 Journal of Computational and Applied Mathematics
5 Numerical Algorithms
5 Journal of Mathematical Imaging and Vision
5 Mathematical Programming Computation
4 Inverse Problems
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
3 Foundations of Computational Mathematics
3 Journal of Machine Learning Research (JMLR)
3 Optimization Letters
2 Mathematics of Computation
2 Automatica
2 Journal of Optimization Theory and Applications
2 SIAM Journal on Numerical Analysis
2 Multidimensional Systems and Signal Processing
2 Journal of Global Optimization
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 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 Mathematics of Operations Research
1 Nonlinear Analysis. Theory, Methods & Applications. Series A: Theory and Methods
1 Operations Research Letters
1 Circuits, Systems, and Signal Processing
1 Applied Mathematics and Mechanics. (English Edition)
1 Constructive Approximation
1 Signal Processing
1 Machine Learning
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 Advances in Computational 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 Journal of Industrial and Management Optimization
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