A conjugate subgradient algorithm with adaptive preconditioning for the least absolute shrinkage and selection operator minimization. (English) Zbl 1378.65091
Summary: This paper describes a new efficient conjugate subgradient algorithm which minimizes a convex function containing a least squares fidelity term and an absolute value regularization term. This method is successfully applied to the inversion of ill-conditioned linear problems, in particular for computed tomography with the dictionary learning method. A comparison with other state-of-art methods shows a significant reduction of the number of iterations, which makes this algorithm appealing for practical use.
MSC:
| 65F20 | Numerical solutions to overdetermined systems, pseudoinverses |
| 65F22 | Ill-posedness and regularization problems in numerical linear algebra |
| 65K05 | Numerical mathematical programming methods |
| 90C25 | Convex programming |
| 65F08 | Preconditioners for iterative methods |
| 92C55 | Biomedical imaging and signal processing |
Keywords:
conjugate subgradient algorithm; adaptive preaondibioning; least absolute shrinkage; regularization; ill-conditioned linear problems; numerical examples; computed tomographyReferences:
| [1] | F. Bach, R. Jenatton, J. Mairal, and G. Obozinski, “Optimization with sparsity-inducing penalties,” Foundations Trends Machine Learning 4 (1), 1-106 (2011). · Zbl 06064248 · doi:10.1561/2200000015 |
| [2] | A. N. Tikhonov, “On the stability of inverse problems,” Dokl. Akad. Nauk SSSR 5 (39), 195-198 (1943). |
| [3] | A. Chambolle and T. Pock, “A first-order primal-dual algorithm for convex problems with applications to imaging,” J. Math. Imaging Vision 40 (1), 120-145 (2011). · Zbl 1255.68217 · doi:10.1007/s10851-010-0251-1 |
| [4] | E. Y. Sidky, J. H. Jørgensen, and X. Pan, “Convex optimization problem prototyping for image reconstruction in computed tomography with the Chambolle-Pock algorithm,” Phys. Med. Biol. 57 (10), 3065-3091 (2012). · doi:10.1088/0031-9155/57/10/3065 |
| [5] | P. L. Combettes and J.-C. Pesquet, “Proximal Splitting Methods in Signal Processing,” ArXiv e-prints, Dec. 2009. · Zbl 1242.90160 |
| [6] | R. Tibshirani, “Regression shrinkage and selection via the lasso,” J. R. Stat. Soc. Ser. B (Methodological) 58 (1), 267-288 (1996). · Zbl 0850.62538 |
| [7] | L. I. Rudin, S. Osher, and E. Fatemi, “Nonlinear total variation based noise removal algorithms,” Phys. D: Nonlinear Phenom. 60 (1-4), 259-268 (1992). · Zbl 0780.49028 · doi:10.1016/0167-2789(92)90242-F |
| [8] | Selesnick, I. W.; Figueiredo, M. A. T., Signal restoration with overcomplete wavelet transforms: Comparison of analysis and synthesis priors (2009) |
| [9] | A. Beck and M. Teboulle, “Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems,” IEEE Trans. Image Process. 18, 2419-2434 (2009). · Zbl 1371.94049 · doi:10.1109/TIP.2009.2028250 |
| [10] | Y. Nesterov, “A method of solving a convex programming problem with convergence rate <Emphasis Type=”Italic“>O(1/sqr(<Emphasis Type=”Italic“>k)),” Sov. Math. Dokl. 27, 372-376 (1983). · Zbl 0535.90071 |
| [11] | S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, “Distributed optimization and statistical learning via the alternating direction method of multipliers,” Found. Trends Machine Learn. 3 (1), 1-122, (2011). · Zbl 1229.90122 · doi:10.1561/2200000016 |
| [12] | S. Boyd, L. Xiao, and A. Mutapcic, “Subgradient methods,” Notes for EE392o (Stanford Univ. 2003). |
| [13] | S. Bubeck, “Theory of convex optimization for machine learning,” arXiv:1405.4980 (2014). |
| [14] | A. Mirone and P. Paleo, “Python script: Csg.py.” https://github.com/pierrepaleo/csg |
| [15] | A. Mirone, E. Brun, and P. Coan, “A dictionary learning approach with overlap for the low dose computed tomography reconstruction and its vectorial application to differential phase tomography,” PLoS ONE 9 (12), e114325 (2014). doi 10.1371/journal.pone.0114325 · doi:10.1371/journal.pone.0114325 |
| [16] | E. J. Candés, J. K. Romberg, and T. Tao, “Stable signal recovery from incomplete and inaccurate measurements,” Commun. Pure Appl. Math. 59 (8), 1207-1223 (2006). · Zbl 1098.94009 · doi:10.1002/cpa.20124 |
| [17] | P. Paleo and A. Mirone, “Ring artifacts correction in compressed sensing tomographic reconstruction,” arXiv:1502.01480 (2015). |
| [18] | A. Mirone, E. Brun, E. Gouillart, P. Tafforeau, and J. Kieffer, “The PyHST2 hybrid distributed code for high speed tomographic reconstruction with iterative reconstruction and a priori knowledge capabilities,” Nuclear Instrum. Methods Phys. Res. Sect B: Beam Interactions Materials Atoms 324, 41-48 (2014). · doi:10.1016/j.nimb.2013.09.030 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
