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 72 articles )
Showing results 1 to 20 of 72.
Sorted by year (- Guo, Ling; Narayan, Akil; Zhou, Tao; Chen, Yuhang: Stochastic collocation methods via $\ell_1$ minimization using randomized quadratures (2017)
- Zhang, Na; Li, Qia: On optimal solutions of the constrained $\ell_0$ regularization and its penalty problem (2017)
- 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)
- Hager, William W.; Phan, Dzung T.; Zhu, Jiajie: Projection algorithms for nonconvex minimization with application to sparse principal component analysis (2016)
- Li, Guotu; Iskandarani, Mohamed; Hénaff, Matthieu Le; Winokur, Justin; Le Ma^ıtre, Olivier P.; Knio, Omar M.: Quantifying initial and wind forcing uncertainties in the gulf of Mexico (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)
- Potts, Daniel; Volkmer, Toni: Sparse high-dimensional FFT based on rank-1 lattice sampling (2016)
- Shefi, Ron; Teboulle, Marc: A dual method for minimizing a nonsmooth objective over one smooth inequality constraint (2016)
- Shen, Yuan; Wang, Hongyong: New augmented Lagrangian-based proximal point algorithm for convex optimization with equality constraints (2016)
- Yang, Xiu; Lei, Huan; Baker, Nathan A.; Lin, Guang: Enhancing sparsity of Hermite polynomial expansions by iterative rotations (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)
- Hampton, Jerrad; Doostan, Alireza: Compressive sampling of polynomial chaos expansions: convergence analysis and sampling strategies (2015)
- Jakeman, J.D.; Eldred, M.S.; Sargsyan, K.: Enhancing $\ell_1$-minimization estimates of polynomial chaos expansions using basis selection (2015)