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 196 articles , 2 standard articles )
Showing results 1 to 20 of 196.
Sorted by year (- Li, Hailong; Ding, Liang: Generalized conditional gradient method for elastic-net regularization (2022)
- Perez, Guillaume; Ament, Sebastian; Gomes, Carla; Barlaud, Michel: Efficient projection algorithms onto the weighted (\ell_1) ball (2022)
- 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)
- Cai, Yun; Wang, Ying: Convergence and stability analysis of iteratively reweighted least squares for noisy block sparse recovery (2021)
- Calatroni, Luca; Garrigos, Guillaume; Rosasco, Lorenzo; Villa, Silvia: Accelerated iterative regularization via dual diagonal descent (2021)
- Cleaves, Helen; Alexanderian, Alen; Saad, Bilal: Structure exploiting methods for fast uncertainty quantification in multiphase flow through heterogeneous media (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)
- 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)
- Pan, Lili; Chen, Xiaojun: Group sparse optimization for images recovery using capped folded concave functions (2021)
- Shehu, Yekini; Dong, Qiao-Li; Liu, Lu-Lu; Yao, Jen-Chih: New strong convergence method for the sum of two maximal monotone operators (2021)
- Tendero, Yohann; Ciril, Igor; Darbon, Jérôme; Serna, Susana: An algorithm solving compressive sensing problem based on maximal monotone operators (2021)
- Thesing, L.; Hansen, A. C.: Non-uniform recovery guarantees for binary measurements and infinite-dimensional compressed sensing (2021)
- Van Hieu, Dang; Anh, Pham Ky; Ha, Nguyen Hai: Regularization proximal method for monotone variational inclusions (2021)