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 183 articles , 2 standard articles )
Showing results 1 to 20 of 183.
Sorted by year (- Adcock, Ben; Dexter, Nick: The gap between theory and practice in function approximation with deep neural networks (2021)
- Beinert, Robert; Steidl, Gabriele: Robust PCA via regularized \textscReaperwith a matrix-free proximal algorithm (2021)
- Calatroni, Luca; Garrigos, Guillaume; Rosasco, Lorenzo; Villa, Silvia: Accelerated iterative regularization via dual diagonal descent (2021)
- Cortiella, Alexandre; Park, Kwang-Chun; Doostan, Alireza: Sparse identification of nonlinear dynamical systems via reweighted (\ell_1)-regularized least squares (2021)
- Courbot, Jean-Baptiste; Colicchio, Bruno: A fast homotopy algorithm for gridless sparse recovery (2021)
- Jiang, Shan; Fang, Shu-Cherng; Jin, Qingwei: Sparse solutions by a quadratically constrained (\ellq) ((0 < q< 1)) minimization model (2021)
- Li, Xinxin; Pong, Ting Kei; Sun, Hao; Wolkowicz, Henry: A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem (2021)
- Luiken, Nick; van Leeuwen, Tristan: Relaxed regularization for linear inverse problems (2021)
- Lüthen, Nora; Marelli, Stefano; Sudret, Bruno: Sparse polynomial chaos expansions: literature survey and benchmark (2021)
- Nakatsukasa, Yuji; Townsend, Alex: Error localization of best (L_1) polynomial approximants (2021)
- Thesing, L.; Hansen, A. C.: Non-uniform recovery guarantees for binary measurements and infinite-dimensional compressed sensing (2021)
- Yu, Peiran; Pong, Ting Kei; Lu, Zhaosong: Convergence rate analysis of a sequential convex programming method with line search for a class of constrained difference-of-convex optimization problems (2021)
- Zeng, Liaoyuan; Yu, Peiran; Pong, Ting Kei: Analysis and algorithms for some compressed sensing models based on L1/L2 minimization (2021)
- Abubakar, Auwal Bala; Kumam, Poom; Mohammad, Hassan: A note on the spectral gradient projection method for nonlinear monotone equations with applications (2020)
- Daskalakis, Emmanouil; Herrmann, Felix J.; Kuske, Rachel: Accelerating sparse recovery by reducing chatter (2020)
- Ding, Liang; Han, Weimin: A projected gradient method for (\alpha\ell_1-\beta\ell_2) sparsity regularization (2020)
- Estrin, Ron; Friedlander, Michael P.: A perturbation view of level-set methods for convex optimization (2020)
- Fairbanks, Hillary R.; Jofre, Lluís; Geraci, Gianluca; Iaccarino, Gianluca; Doostan, Alireza: Bi-fidelity approximation for uncertainty quantification and sensitivity analysis of irradiated particle-laden turbulence (2020)
- Jiang, Shan; Fang, Shu-Cherng; Nie, Tiantian; Xing, Wenxun: A gradient descent based algorithm for (\ell_p) minimization (2020)
- Keshavarzzadeh, Vahid; Kirby, Robert M.; Narayan, Akil: Generation of nested quadrature rules for generic weight functions via numerical optimization: application to sparse grids (2020)