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 96 articles )
Showing results 1 to 20 of 96.
Sorted by year (- Yu, Yongchao; Peng, Jigen: The matrix splitting based proximal fixed-point algorithms for quadratically constrained $\ell_1$ minimization and Dantzig selector (2018)
- Aravkin, Aleksandr; Burke, James V.; Ljung, Lennart; Lozano, Aurelie; Pillonetto, Gianluigi: Generalized Kalman smoothing: modeling and algorithms (2017)
- Bastounis, Alexander; Hansen, Anders C.: On the absence of uniform recovery in many real-world applications of compressed sensing and the restricted isometry property and nullspace property in levels (2017)
- Bouwmans, Thierry; Sobral, Andrews; Javed, Sajid; Jung, Soon Ki; Zahzah, El-Hadi: Decomposition into low-rank plus additive matrices for background/foreground separation: a review for a comparative evaluation with a large-scale dataset (2017)
- Boyd, Nicholas; Schiebinger, Geoffrey; Recht, Benjamin: The alternating descent conditional gradient method for sparse inverse problems (2017)
- Drusvyatskiy, D.; Krislock, N.; Voronin, Yuen-Lam; Wolkowicz, H.: Noisy Euclidean distance realization: robust facial reduction and the Pareto frontier (2017)
- Guo, Ling; Narayan, Akil; Zhou, Tao; Chen, Yuhang: Stochastic collocation methods via $\ell_1$ minimization using randomized quadratures (2017)
- Hart, J.L.; Alexanderian, A.; Gremaud, P.A.: Efficient computation of Sobol’ indices for stochastic models (2017)
- Hu, Jun; Zhang, Shudao: Global sensitivity analysis based on high-dimensional sparse surrogate construction (2017)
- Karimi, Sahar; Vavasis, Stephen: IMRO: A proximal quasi-Newton method for solving $\ell_1$-regularized least squares problems (2017)
- Lu, Zhaosong: Randomized block proximal damped Newton method for composite self-concordant minimization (2017)
- Lu, Zhaosong; Xiao, Lin: A randomized nonmonotone block proximal gradient method for a class of structured nonlinear programming (2017)
- Xia, Yu; Li, Song: Nonuniform recovery of fusion frame structured sparse signals (2017)
- Zhang, Na; Li, Qia: On optimal solutions of the constrained $\ell_0$ regularization and its penalty problem (2017)
- Abusag, Nadia M.; Chappell, David J.: On sparse reconstructions in near-field acoustic holography using the method of superposition (2016)
- 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)
- Deepa, K.G.; Ambat, Sooraj K.; Hari, K.V.S.: Fusion of sparse reconstruction algorithms for multiple measurement vectors (2016)