zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
On the convergence of primal-dual hybrid gradient algorithms for total variation image restoration. (English) Zbl 1255.68210
Summary: In this paper we establish the convergence of a general primal-dual method for nonsmooth convex optimization problems whose structure is typical in the imaging framework, as, for example, in the total variation image restoration problems. When the steplength parameters are a priori selected sequences, the convergence of the scheme is proved by showing that it can be considered as an ϵ-subgradient method on the primal formulation of the variational problem. Our scheme includes as special case the method recently proposed by Zhu and Chan for Total Variation image restoration from data degraded by Gaussian noise. Furthermore, the convergence hypotheses enable us to apply the same scheme also to other restoration problems, as the denoising and deblurring of images corrupted by Poisson noise, where the data fidelity function is defined as the generalized Kullback-Leibler divergence or the edge preserving removal of impulse noise. The numerical experience shows that the proposed scheme with a suitable choice of the steplength sequences performs well with respect to state-of-the-art methods, especially for Poisson denoising problems, and it exhibits fast initial and asymptotic convergence.
MSC:
68U10Image processing (computing aspects)
90C25Convex programming
68U05Computer graphics; computational geometry
References:
[1]Arrow, K.J., Hurwicz, L., Uzawa, H.: Studies in Linear and Non-Linear Programming, vol. II. Stanford University Press, Stanford (1958)
[2]Aujol, J.F.: Some first-order algorithms for total variation based image restoration. J. Math. Imaging Vis. 34(3), 307–327 (2009) · Zbl 05788088 · doi:10.1007/s10851-009-0149-y
[3]Bardsley, J.M., Luttman, A.: Total variation-penalized Poisson likelihood estimation for ill-posed problems. Adv. Comput. Math. 31(1–3), 35–59 (2009) · Zbl 1171.94001 · doi:10.1007/s10444-008-9081-8
[4]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) · doi:10.1109/TIP.2009.2028250
[5]Bertsekas, D.: Convex Optimization Theory. Scientific, Athena (2009)
[6]Bonettini, S., Ruggiero, V.: An alternating extragradient method for total variation based image restoration from Poisson data. Inverse Probl. 27, 095001 (2011)
[7]Brune, C., Sawatzky, A., Wübbeling, F., Kösters, T., Burger, M.: Forward–Backward EM-TV methods for inverse problems with Poisson noise. http://wwwmath.uni-muenster.de/num/publications/2009/BBSKW09/ (2009)
[8]Chambolle, A.: An algorithm for total variation minimization and applications. J. Math. Imaging Vis. 20, 89–97 (2004) · Zbl 02060336 · doi:10.1023/B:JMIV.0000011321.19549.88
[9]Chambolle, A.: Total variation minimization and a class of binary MRF models. In: EMMCVPR 05. Lecture Notes in Computer Sciences, vol. 3757, pp. 136–152 (2005)
[10]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
[11]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 (1999) · Zbl 0929.68118 · doi:10.1137/S1064827596299767
[12]Charbonnier, P., Blanc-Féraud, L., Aubert, G., Barlaud, A.: Deterministic edge-preserving regularization in computed imaging. IEEE Trans. Image Process. 6, 298–311 (1997) · doi:10.1109/83.551699
[13]Correa, R., Lemaréchal, C.: Convergence of some algorithms for convex minimization. Math. Program. 62, 261–275 (1993) · Zbl 0805.90083 · doi:10.1007/BF01585170
[14]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
[15]Ekeland, I., Témam, R.: Convex Analysis and Variational Problems. SIAM, Philadelphia (1999)
[16]Esser, E., Zhang, X., Chan, T.: A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM J. Imaging Sci. 3(4), 1015–1046 (2010) · Zbl 1206.90117 · doi:10.1137/09076934X
[17]Geman, S., Geman, D.: Stochastic relaxation, Gibbs distribution and the Bayesian restoration of images. IEEE Trans. Pattern Anal. Mach. Intell. 6, 721–741 (1984) · Zbl 0573.62030 · doi:10.1109/TPAMI.1984.4767596
[18]Goldfarb, D., Yin, W.: Second-order cone programming methods for total variation based image restoration. SIAM J. Sci. Comput. 27(2), 622–645 (2005) · Zbl 1094.68108 · doi:10.1137/040608982
[19]Goldstein, T., Osher, S.: The split Bregman method for L1 regularized problems. SIAM J. Imaging Sci. 2, 323–343 (2009) · Zbl 1177.65088 · doi:10.1137/080725891
[20]Larsson, T., Patriksson, M., Strömberg, A.B.: On the convergence of conditional ϵ-subgradient methods for convex programs and convex–concave saddle-point problems. Eur. J. Oper. Res. 151, 461–473 (2003) · Zbl 1053.90107 · doi:10.1016/S0377-2217(02)00629-X
[21]Le, T., Chartrand, R., Asaki, T.J.: A variational approach to reconstructing images corrupted by Poisson noise. J. Math. Imaging Vis. 27, 257–263 (2007) · doi:10.1007/s10851-007-0652-y
[22]Osher, S., Burger, M., Goldfarb, D., Xu, J., Yin, W.: An iterative regularization method for total variation-based image restoration. SIAM J. Multiscale Model. Simul. 4(2), 460–489 (2005) · Zbl 1090.94003 · doi:10.1137/040605412
[23]Robinson, S.M.: Linear convergence of epsilon-subgradient descent methods for a class of convex functions. Math. Program., Ser. A 86, 41–50 (1999) · Zbl 1029.90056 · doi:10.1007/s101070050078
[24]Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)
[25]Rudin, L., 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
[26]Setzer, S., Steidl, G., Teuber, T.: Deblurring Poissonian images by split Bregman techniques. J. Vis. Commun. Image Represent. 21, 193–199 (2010) · Zbl 05742901 · doi:10.1016/j.jvcir.2009.10.006
[27]Shepp, L.A., Vardi, Y.: Maximum likelihood reconstruction for emission tomography. IEEE Trans. Med. Imaging 1, 113–122 (1982) · doi:10.1109/TMI.1982.4307558
[28]Willett, R.M., Nowak, R.D.: Platelets: a multiscale approach for recovering edges and surfaces in photon limited medical imaging. IEEE Trans. Med. Imaging 22, 332–350 (2003) · doi:10.1109/TMI.2003.809622
[29]Yu, G., Qi, L., Dai, Y.: On nonmonotone Chambolle gradient projection algorithms for total variation image restoration. J. Math. Imaging Vis. 35, 143–154 (2009) · Zbl 05788099 · doi:10.1007/s10851-009-0160-3
[30]Zanella, R., Boccacci, P., Zanni, L., Bertero, M.: Efficient gradient projection methods for edge-preserving removal of Poisson noise. Inverse Probl. 25, 045010 (2009)
[31]Zhu, M., Chan, T.F.: An efficient primal–dual hybrid gradient algorithm for Total Variation image restoration. CAM Report 08-34, UCLA (2008)
[32]Zhu, M., Wright, S.J., Chan, T.F.: Duality-based algorithms for total-variation-regularized image restoration. Comput. Optim. Appl. 47, 377–400 (2008) · Zbl 1208.90165 · doi:10.1007/s10589-008-9225-2