SPGL1
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.
Keywords for this software
References in zbMATH (referenced in 59 articles )
Showing results 1 to 20 of 59.
Sorted by year (- Ascher, Uri; Roosta-Khorasani, Farbod: Algorithms that satisfy a stopping criterion, probably (2016)
- Bleichrodt, Folkert; van Leeuwen, Tristan; Palenstijn, Willem Jan; van Aarle, Wim; Sijbers, Jan; Batenburg, K.Joost: Easy implementation of advanced tomography algorithms using the ASTRA toolbox with spot operators (2016)
- Chen, Xiaojun; Lu, Zhaosong; Pong, Ting Kei: Penalty methods for a class of non-Lipschitz optimization problems (2016)
- Condat, Laurent: Fast projection onto the simplex and the $l_1$ ball (2016)
- Gataric, Milana; Poon, Clarice: A practical guide to the recovery of wavelet coefficients from Fourier measurements (2016)
- Giryes, Raja: Sampling in the analysis transform domain (2016)
- Liu, Ya-Feng; Ma, Shiqian; Dai, Yu-Hong; Zhang, Shuzhong: A smoothing SQP framework for a class of composite $L_q$ minimization over polyhedron (2016)
- Nikolova, Mila: Relationship between the optimal solutions of least squares regularized with $\ell_0$-norm and constrained by $k$-sparsity (2016)
- Adcock, Ben; Hansen, Anders C.; Roman, Bogdan: The quest for optimal sampling: computationally efficient, structure-exploiting measurements for compressed sensing (2015)
- Birgin, E.G.; Martínez, J.M.; Prudente, L.F.: Optimality properties of an augmented Lagrangian method on infeasible problems (2015)
- Landi, G.: A modified Newton projection method for $\ell _1$-regularized least squares image deblurring (2015)
- Lei, H.; Yang, X.; Zheng, B.; Lin, G.; Baker, N.A.: Constructing surrogate models of complex systems with enhanced sparsity: quantifying the influence of conformational uncertainty in biomolecular solvation (2015)
- Li, Xinxin; Yuan, Xiaoming: A proximal strictly contractive Peaceman-Rachford splitting method for convex programming with applications to imaging (2015)
- Li, Yusheng; Xie, Xinchang; Yang, Zhouwang: Alternating direction method of multipliers for solving dictionary learning models (2015)
- Nicodème, Marc; Turcu, Flavius; Dossal, Charles: Optimal dual certificates for noise robustness bounds in compressive sensing (2015)
- Quoc, Tran-Dinh; Kyrillidis, Anastasios; Cevher, Volkan: Composite self-concordant minimization (2015)
- Yan, Liang; Guo, Ling: Stochastic collocation algorithms using $l_1$-minimization for Bayesian solution of inverse problems (2015)
- Ames, Brendan P.W.: Guaranteed clustering and biclustering via semidefinite programming (2014)
- Aybat, N.S.; Iyengar, G.: A unified approach for minimizing composite norms (2014)
- Cao, Shuhan; Xiao, Yunhai; Zhu, Hong: Linearized alternating directions method for $\ell_1$-norm inequality constrained $\ell_1$-norm minimization (2014)