Abstract
Many imaging problems can be formulated as inverse problems expressed as finite-dimensional optimization problems. These optimization problems generally consist of minimizing the sum of a data fidelity and regularization terms. In Darbon (SIAM J. Imag. Sci. 8:2268–2293, 2015), Darbon and Meng, (On decomposition models in imaging sciences and multi-time Hamilton-Jacobi partial differential equations, arXiv preprint arXiv:1906.09502, 2019), connections between these optimization problems and (multi-time) Hamilton-Jacobi partial differential equations have been proposed under the convexity assumptions of both the data fidelity and regularization terms. In particular, under these convexity assumptions, some representation formulas for a minimizer can be obtained. From a Bayesian perspective, such a minimizer can be seen as a maximum a posteriori estimator. In this chapter, we consider a certain class of non-convex regularizations and show that similar representation formulas for the minimizer can also be obtained. This is achieved by leveraging min-plus algebra techniques that have been originally developed for solving certain Hamilton-Jacobi partial differential equations arising in optimal control. Note that connections between viscous Hamilton-Jacobi partial differential equations and Bayesian posterior mean estimators with Gaussian data fidelity terms and log-concave priors have been highlighted in Darbon and Langlois, (On Bayesian posterior mean estimators in imaging sciences and Hamilton-Jacobi partial differential equations, arXiv preprint arXiv:2003.05572, 2020). We also present similar results for certain Bayesian posterior mean estimators with Gaussian data fidelity and certain non-log-concave priors using an analogue of min-plus algebra techniques.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Akian, M., Bapat, R., Gaubert, S.: Max-plus algebra. In: Handbook of Linear Algebra, 39 (2006)
Akian, M., Gaubert, S., Lakhoua, A.: The max-plus finite element method for solving deterministic optimal control problems: basic properties and convergence analysis. SIAM J. Control. Optim. 47, 817–848 (2008)
Allain, M., Idier, J., Goussard, Y.: On global and local convergence of half-quadratic algorithms. IEEE Trans. Image Process. 15, 1130–1142 (2006)
Aubert, G., Kornprobst, P.: Mathematical Problems in Image Processing. Springer (2002)
Aujol, J.-F., Aubert, G., Blanc-Féraud, L., Chambolle, A.: Image decomposition application to SAR images. In: L.D. Griffin, Lillholm, M. (eds.) Scale Space Methods in Computer Vision. Springer, Berlin/Heidelberg, pp. 297–312 (2003)
Aujol, J.-F., Aubert, G., Blanc-Féraud, L., Chambolle, A.: Image decomposition into a bounded variation component and an oscillating component. J. Math. Imaging Vision 22, 71–88 (2005)
Bardi, M., Capuzzo-Dolcetta, I.: Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations. Systems & Control: Foundations & Applications, Birkhäuser Boston, Inc., Boston (1997). With appendices by Maurizio Falcone and Pierpaolo Soravia
Bardi, M., Evans, L.: On Hopf’s formulas for solutions of Hamilton-Jacobi equations. Nonlinear Anal. Theory Methods Appl. 8, 1373–1381 (1984)
Barles, G.: Solutions de viscosité des équations de Hamilton-Jacobi. Mathématiques et Applications. Springer, Berlin/Heidelberg (1994)
Barron, E., Evans, L., Jensen, R.: Viscosity solutions of Isaacs’ equations and differential games with Lipschitz controls. J. Differ. Equ. 53, 213–233 (1984)
Bouman, C., Sauer, K.: A generalized gaussian image model for edge-preserving map estimation. IEEE Trans. Trans. Signal Process. 2, 296–310 (1993)
Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell. 23, 1222–1239 (2001)
Burger, M., Lucka, F.: Maximum a posteriori estimates in linear inverse problems with log-concave priors are proper bayes estimators. Inverse Probl. 30, 114004 (2014)
Burger, Y.D.M., Sciacchitano, F.: Bregman cost for non-gaussian noise. arXiv preprint arXiv:1608.07483 (2016)
Chambolle, A., Darbon, J.: On total variation minimization and surface evolution using parametric maximum flows. Int. J. Comput. Vis. 84, 288–307 (2009)
Chambolle, A., Novaga, M., Cremers, D., Pock, T.: An introduction to total variation for image analysis. In: Theoretical Foundations and Numerical Methods for Sparse Recovery, De Gruyter (2010)
Chambolle, A., Pock, T.: An introduction to continuous optimization for imaging. Acta Numer. 25, 161–319 (2016)
Champagnat, F., Idier, J.: A connection between half-quadratic criteria and em algorithms. IEEE Signal Processing Lett. 11, 709–712 (2004)
Chan, T.F., Esedoglu, S., Nikolova, M.: Algorithms for finding global minimizers of image segmentation and denoising models. SIAM J. Appl. Math. 66, 1632–1648 (2006)
Chan, T.F., Shen, J.: Image processing and analysis, Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2005). Variational, PDE, wavelet, and stochastic methods
Chan, T.F., Vese, L.A.: Active contours without edges. IEEE Trans. Image Process. 10, 266–277 (2001)
Charbonnier, P., Blanc-Feraud, L., Aubert, G., Barlaud, M.: Deterministic edge-preserving regularization in computed imaging. IEEE Trans. Image Process. 6, 298–311 (1997)
Crandall, M.G., Ishii, H., Lions, P.-L.: User’s guide to viscosity solutions of second order partial differential equations. Bull. Am. Math. Soc. 27, 1–67 (1992)
Darbon, J.: On convex finite-dimensional variational methods in imaging sciences and Hamilton–Jacobi equations. SIAM J. Imag. Sci. 8, 2268–2293 (2015)
Darbon, J., Ciril, I., Marquina, A., Chan, T.F., Osher, S.: A note on the bregmanized total variation and dual forms. In: 2009 16th IEEE International Conference on Image Processing (ICIP), Nov 2009, pp. 2965–2968
Darbon, J., Langlois, G.P.: On Bayesian posterior mean estimators in imaging sciences and Hamilton-Jacobi partial differential equations. arXiv preprint arXiv: 2003.05572 (2020)
Darbon, J., Meng, T.: On decomposition models in imaging sciences and multi-time Hamilton-Jacobi partial differential equations. SIAM Journal on Imaging Sciences. 13(2), 971–1014 (2020). https://doi.org/10.1137/19M1266332
Darbon, J., Sigelle, M.: Image restoration with discrete constrained total variation part I: Fast and exact optimization. J. Math. Imaging Vision 26, 261–276 (2006)
Demoment, G.: Image reconstruction and restoration: Overview of common estimation structures and problems. IEEE Trans. Acoust. Speech Signal Process. 37, 2024–2036 (1989)
Dou, Z., Song, M., Gao, K., Jiang, Z.: Image smoothing via truncated total variation. IEEE Access 5, 27337–27344 (2017)
Dower, P.M., McEneaney, W.M., Zhang, H.: Max-plus fundamental solution semigroups for optimal control problems. In: 2015 Proceedings of the Conference on Control and its Applications. SIAM, 2015, pp. 368–375
Duda, R.O., Hart, P.E., Stork, D.G.: Pattern Classification. Wiley (2012)
Evans, L.C.: Partial differential equations, vol. 19 of Graduate Studies in Mathematics, 2nd edn. American Mathematical Society, Providence (2010)
Fleming, W., McEneaney, W.: A max-plus-based algorithm for a Hamilton–Jacobi–Bellman equation of nonlinear filtering. SIAM J. Control. Optim. 38, 683–710 (2000)
Fleming, W.H., Soner, H.M.: Controlled Markov Processes and Viscosity Solutions, vol. 25. Springer Science & Business Media (2006)
Floudas, C.A., Pardalos, P.M. (eds.): Encyclopedia of Optimization, 2nd edn. (2009)
Gaubert, S., McEneaney, W., Qu, Z.: Curse of dimensionality reduction in max-plus based approximation methods: Theoretical estimates and improved pruning algorithms. In: 2011 50th IEEE Conference on Decision and Control and European Control Conference. IEEE, 2011, pp. 1054–1061
Geman, D., Yang, C.: Nonlinear image recovery with half-quadratic regularization. IEEE Trans. Image Process. 4, 932–946 (1995)
Geman, D., Reynolds, G.: Constrained restoration and the recovery of discontinuities. IEEE Trans. Pattern Anal. Mach. Intell. 14, 367–383 (1992)
Gribonval, R.: Should penalized least squares regression be interpreted as maximum a posteriori estimation? IEEE Trans. Signal Process. 59, 2405–2410 (2011)
Gribonval, R., Machart, P.: Reconciling” priors” &” priors” without prejudice? In: Advances in Neural Information Processing Systems, 2013, pp. 2193–2201
Gribonval, R., Nikolova, M.: On bayesian estimation and proximity operators, arXiv preprint arXiv:1807.04021 (2018)
Hochbaum, D.S.: An efficient algorithm for image segmentation, Markov random fields and related problems. J. ACM 48, 686–701 (2001)
Hopf, E.: Generalized solutions of non-linear equations of first order. J. Math. Mech. 14, 951–973 (1965)
Idier, J.: Convex half-quadratic criteria and interacting auxiliary variables for image restoration. IEEE Trans. Image Process. 10, 1001–1009 (2001)
Kay, S.M.: Fundamentals of Statistical Signal Processing. Prentice Hall PTR (1993)
Kolokoltsov, V.N., Maslov, V.P.: Idempotent analysis and its applications, vol. 401 of Mathematics and its Applications. Kluwer Academic Publishers Group, Dordrecht (1997) Translation of ıt Idempotent analysis and its application in optimal control (Russian), “Nauka” Moscow, 1994 [ MR1375021 (97d:49031)], Translated by V. E. Nazaikinskii, With an appendix by Pierre Del Moral
Le Guen, V.: Cartoon + Texture Image Decomposition by the TV-L1yModel. Image Process. Line 4, 204–219 (2014)
Likas, A.C., Galatsanos, N.P.: A variational approach for bayesian blind image deconvolution. IEEE Trans. Signal Process. 52, 2222–2233 (2004)
Lions, P.L., Rochet, J.-C.: Hopf formula and multitime Hamilton-Jacobi equations. Proc. Am. Math. Soc. 96, 79–84 (1986)
Louchet, C.: Modèles variationnels et bayésiens pour le débruitage d’images: de la variation totale vers les moyennes non-locales. Ph.D. thesis, Université René Descartes-Paris V (2008)
Louchet, C., Moisan, L.: Posterior expectation of the total variation model: properties and experiments. SIAM J. Imaging Sci. 6, 2640–2684 (2013)
McEneaney, W.: Max-plus methods for nonlinear control and estimation. Springer Science & Business Media (2006)
McEneaney, W.: A curse-of-dimensionality-free numerical method for solution of certain HJB PDEs. SIAM J. Control. Optim. 46, 1239–1276 (2007)
McEneaney, W.M., Deshpande, A., Gaubert, S.: Curse-of-complexity attenuation in the curse-of-dimensionality-free method for HJB PDEs. In: 2008 American Control Conference. IEEE, 2008, pp. 4684–4690
McEneaney, W.M., Kluberg, L.J.: Convergence rate for a curse-of-dimensionality-free method for a class of HJB PDEs. SIAM J. Control. Optim. 48, 3052–3079 (2009)
Nikolova, M., Chan, R.H.: The equivalence of half-quadratic minimization and the gradient linearization iteration. IEEE Trans. Image Process. 16, 1623–1627 (2007)
Nikolova, M., Ng, M.: Fast image reconstruction algorithms combining half-quadratic regularization and preconditioning. In: Proceedings 2001 International Conference on Image Processing (Cat. No. 01CH37205), vol. 1. IEEE, 2001, pp. 277–280
Nikolova, M., Ng, M.K.: Analysis of half-quadratic minimization methods for signal and image recovery. SIAM J. Sci. Comput. 27, 937–966 (2005)
Osher, S., A. Solé, and Vese, L.: , Image decomposition and restoration using total variation minimization and the H−1 norm, Multiscale Modeling & Simulation, 1 (2003), pp. 349–370.
Rudin, L., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60, 259–268 (1992)
Scherzer, O., Grasmair, M., Grossauer, H., Haltmeier, M., Lenzen, F.: Variational methods in imaging, vol. 167 of Applied Mathematical Sciences. Springer, New York (2009)
Tho, N.: Hopf-Lax-Oleinik type formula for multi-time Hamilton-Jacobi equations. Acta Math. Vietnamica 30, 275–287 (2005)
Vese, L.A., Le Guyader, C.: Variational methods in image processing, Chapman & Hall/CRC Mathematical and Computational Imaging Sciences. CRC Press, Boca Raton (2016)
Winkler, G.: Image Analysis, Random Fields and Dynamic Monte Carlo Methods. Applications of Mathematics. Springer, 2nd edn. (2003)
Acknowledgements
This work was funded by NSF 1820821.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 Springer Nature Switzerland AG
About this entry
Cite this entry
Darbon, J., Langlois, G.P., Meng, T. (2023). Connecting Hamilton-Jacobi Partial Differential Equations with Maximum a Posteriori and Posterior Mean Estimators for Some Non-convex Priors. In: Chen, K., Schönlieb, CB., Tai, XC., Younes, L. (eds) Handbook of Mathematical Models and Algorithms in Computer Vision and Imaging. Springer, Cham. https://doi.org/10.1007/978-3-030-98661-2_56
Download citation
DOI: https://doi.org/10.1007/978-3-030-98661-2_56
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-98660-5
Online ISBN: 978-3-030-98661-2
eBook Packages: Mathematics and StatisticsReference Module Computer Science and Engineering