×

zbMATH — the first resource for mathematics

Implementation of an optimal first-order method for strongly convex total variation regularization. (English) Zbl 1256.65063
The paper presents a practical implementation of an optimal first-order optimization algorithm for large-scale problems. This algorithm is suited for smooth and strongly convex functions. While the underlying algorithm by Y. Nesterov [Math. Program. 103, No. 1 (A), 127–152 (2005; Zbl 1079.90102)] requires the knowledge of two parameters that characterize the smoothness and the strong convexity, the proposed algorithm estimates these parameters during the iteration. This makes the algorithm of practical use. The mechanisms are also allowed for the application to non-strongly convex functions.
The authors test the performance of the algorithm and compare it with two variants of the gradient projection algorithm and a variant of the FISTA-algorithm. They apply the method to total variation regularized tomographic reconstruction of a generic three-dimensional test problem. The software is available as a C-implementation with an interface to MATLAB.

MSC:
65K10 Numerical optimization and variational techniques
65R32 Numerical methods for inverse problems for integral equations
90C30 Nonlinear programming
49J20 Existence theories for optimal control problems involving partial differential equations
49M37 Numerical methods based on nonlinear programming
Software:
Matlab; na28; NESTA; TFOCS; TwIST
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alter, F., Durand, S., Froment, J.: Adapted total variation for artifact free decompression of JPEG images. J. Math. Imaging Vis. 23, 199–211 (2005) · doi:10.1007/s10851-005-6467-9
[2] Barzilai, J., Borwein, J.M.: Two-point step size gradient methods. IMA J. Numer. Anal. 8, 141–148 (1988) · Zbl 0638.65055 · doi:10.1093/imanum/8.1.141
[3] Beck, A., Teboulle, M.: 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
[4] Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2, 183–202 (2009) · Zbl 1175.94009 · doi:10.1137/080716542
[5] Becker, S., Bobin, J., Candès, E.J.: NESTA: a fast and accurate first-order method for sparse recovery. SIAM J. Imaging Sci. 4(1), 1–39 (2011) · Zbl 1209.90265 · doi:10.1137/090756855
[6] Becker, S., Candès, E.J., Grant, M.: Templates for convex cone problems with applications to sparse signal recovery. Math. Program. Comput. 3, 165–218 (2011) · Zbl 1257.90042 · doi:10.1007/s12532-011-0029-5
[7] Bioucas-Dias, J.M., Figueiredo, M.A.T.: A new TwIST: two-step iterative shrinkage/thresholding algorithms for image restoration. IEEE Trans. Image Process. 16(12), 2992–3004 (2007) · Zbl 05516510 · doi:10.1109/TIP.2007.909319
[8] Birgin, E.G., Martínez, J.M., Raydan, M.: Nonmonotone spectral projected gradient methods on convex sets. SIAM J. Optim. 10, 1196–1211 (2000) · Zbl 1047.90077 · doi:10.1137/S1052623497330963
[9] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004) · Zbl 1058.90049
[10] Chambolle, A.: An algorithm for total variation minimization and applications. J. Math. Imaging Vis. 20, 89–97 (2004) · Zbl 1366.94056 · doi:10.1023/B:JMIV.0000011320.81911.38
[11] Chambolle, A.: Total variation minimization and a class of binary MRF models. In: Rangarajan, A., Vemuri, B., Yuille, A.L. (eds.) Energy Minimization Methods in Computer Vision and Pattern Recognition. Lecture Notes in Computer Science, vol. 3757, pp. 136–152. Springer, Berlin (2005)
[12] Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40, 120–145 (2011) · Zbl 1255.68217 · doi:10.1007/s10851-010-0251-1
[13] Chan, T.F., Golub, G.H., Mulet, P.: A nonlinear primal-dual method for total variation-based image restoration. SIAM J. Sci. Comput. 20, 1964–1977 (1998) · Zbl 0929.68118 · doi:10.1137/S1064827596299767
[14] Chan, T.F., Shen, J.: Image Processing and Analysis: Variational, PDE, Wavelet, and Stochastic Methods. SIAM, Philadelphia (2005) · Zbl 1095.68127
[15] Combettes, P.L., Luo, J.: An adaptive level set method for nondifferentiable constrained image recovery. IEEE Trans. Image Process. 11, 1295–1304 (2002) · Zbl 05452843 · doi:10.1109/TIP.2002.804527
[16] Dahl, J., Hansen, P.C., Jensen, S.H., Jensen, T.L.: Algorithms and software for total variation image reconstruction via first-order methods. Numer. Algorithms 53, 67–92 (2010) · Zbl 1181.94009 · doi:10.1007/s11075-009-9310-3
[17] Dai, Y.H., Liao, L.Z.: R-linear convergence of the Barzilai and Borwein gradient method. IMA J. Numer. Anal. 22, 1–10 (2002) · Zbl 1002.65069 · doi:10.1093/imanum/22.1.1
[18] Darbon, J., Sigelle, M.: Image restoration with discrete constrained total variation–Part I: Fast and exact optimization. J. Math. Imaging Vis. 26, 261–276 (2006) · Zbl 05193696 · doi:10.1007/s10851-006-8803-0
[19] Fletcher, R.: Low storage methods for unconstrained optimization. In: Allgower, E.L., Georg, K. (eds.) Computational Solution of Nonlinear Systems of Equations, pp. 165–179. Am. Math. Soc., Providence (1990)
[20] Goldfarb, D., Yin, W.: Second-order cone programming methods for total variation-based image restoration. SIAM J. Sci. Comput. 27, 622–645 (2005) · Zbl 1094.68108 · doi:10.1137/040608982
[21] Grippo, L., Lampariello, F., Lucidi, S.: A nonmonotone line search technique for Newton’s method. SIAM J. Numer. Anal. 23, 707–716 (1986) · Zbl 0616.65067 · doi:10.1137/0723046
[22] Hansen, P.C.: Discrete Inverse Problems: Insight and Algorithms. SIAM, Philadelphia (2010) · Zbl 1197.65054
[23] Herman, G.T.: Fundamentals of Computerized Tomography: Image Reconstruction from Projections, 2nd edn. Springer, New York (2009) · Zbl 1280.92002
[24] Hintermüller, M., Stadler, G.: An infeasible primal-dual algorithm for total bounded variation-based INF-convolution-type image restoration. SIAM J. Sci. Comput. 28, 1–23 (2006) · Zbl 1136.94302 · doi:10.1137/040613263
[25] Jørgensen, J.H.: Tomobox (2010). www.mathworks.com/matlabcentral/fileexchange/28496-tomobox
[26] Kak, A.C., Slaney, M.: Principles of Computerized Tomographic Imaging. SIAM, Philadelphia (2001) · Zbl 0984.92017
[27] Lan, G., Lu, Z., Monteiro, R.D.C.: Primal-dual first-order methods with O(1/) iteration-complexity for cone programming. Math. Program., Ser. A 126(1), 1–29 (2011) · Zbl 1208.90113 · doi:10.1007/s10107-008-0261-6
[28] Nemirovsky, A.S., Yudin, D.B.: Problem Complexity and Method Efficiency in Optimization. Wiley, New York (1983)
[29] Nesterov, Y.: A method for unconstrained convex minimization problem with the rate of convergence O(1/k 2). Sov. Math. Dokl. 269, 543–547 (1983)
[30] Nesterov, Y.: Introductory Lectures on Convex Optimization. Kluwer Academic, Dordrecht (2004) · Zbl 1086.90045
[31] Nesterov, Y.: Smooth minimization of nonsmooth functions. Math. Program., Ser. A 103, 127–152 (2005) · Zbl 1079.90102 · doi:10.1007/s10107-004-0552-5
[32] Nesterov, Y.: Gradient methods for minimizing composite objective function (2007). CORE Discussion Paper No 2007076, www.ecore.be/DPs/dp_1191313936.pdf
[33] Nolet, G. (ed.): Seismic Tomography with Applications in Global Seismology and Exploration Geophysics. Reidel, Dordrecht (1987)
[34] Parrish, R.: getLebedevSphere (2010). www.mathworks.com/matlabcentral/fileexchange/27097-getlebedevsphere
[35] Raydan, M.: The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem. SIAM J. Optim. 7, 26–33 (1997) · Zbl 0898.90119 · doi:10.1137/S1052623494266365
[36] Rudin, L.I., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60, 259–268 (1992) · Zbl 0780.49028 · doi:10.1016/0167-2789(92)90242-F
[37] Schabel, M.: 3D Shepp-Logan phantom (2006). www.mathworks.com/matlabcentral/fileexchange/9416-3d-shepp-logan-phantom
[38] Tseng, P.: On accelerated proximal gradient methods for convex-concave optimization. Manuscript (2008). www.math.washington.edu/\(\sim\)tseng/papers/apgm.pdf
[39] Vandenberghe, L.: Optimization methods for large-scale systems. Lecture Notes (2009). www.ee.ucla.edu/\(\sim\)vandenbe/ee236c.html
[40] Vogel, C.R., Oman, M.E.: Iterative methods for total variation denoising. SIAM J. Sci. Comput. 17, 227–238 (1996) · Zbl 0847.65083 · doi:10.1137/0917016
[41] Weiss, P., Blanc-Féraud, L., Aubert, G.: Efficient schemes for total variation minimization under constraints in image processing. SIAM J. Sci. Comput. 31, 2047–2080 (2009) · Zbl 1191.94029 · doi:10.1137/070696143
[42] Zhu, M., Wright, S.J., Chan, T.F.: Duality-based algorithms for total-variation-regularized image restoration. Comput. Optim. Appl. (2008). doi: 10.1007/s10589-008-9225-2 · Zbl 1208.90165
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.