A convergent difference scheme for the infinity Laplacian: construction of absolutely minimizing Lipschitz extensions

Oberman, Adam

doi:10.1090/S0025-5718-04-01688-6

A convergent difference scheme for the infinity Laplacian: construction of absolutely minimizing Lipschitz extensions
HTML articles powered by AMS MathViewer

by Adam M. Oberman PDF

Math. Comp. 74 (2005), 1217-1230 Request permission

Abstract:

This article considers the problem of building absolutely minimizing Lipschitz extensions to a given function. These extensions can be characterized as being the solution of a degenerate elliptic partial differential equation, the “infinity Laplacian”, for which there exist unique viscosity solutions. A convergent difference scheme for the infinity Laplacian equation is introduced, which arises by minimizing the discrete Lipschitz constant of the solution at every grid point. Existence and uniqueness of solutions to the scheme is shown directly. Solutions are also shown to satisfy a discrete comparison principle. Solutions are computed using an explicit iterative scheme which is equivalent to solving the parabolic version of the equation.

References

Luis Alvarez, Frédéric Guichard, Pierre-Louis Lions, and Jean-Michel Morel, Axioms and fundamental equations of image processing, Arch. Rational Mech. Anal. 123 (1993), no. 3, 199–257. MR 1225209, DOI 10.1007/BF00375127
Gunnar Aronsson, Extension of functions satisfying Lipschitz conditions, Ark. Mat. 6 (1967), 551–561 (1967). MR 217665, DOI 10.1007/BF02591928
Gunnar Aronsson, On the partial differential equation $u_{x}{}^{2}\!u_{xx} +2u_{x}u_{y}u_{xy}+u_{y}{}^{2}\!u_{yy}=0$, Ark. Mat. 7 (1968), 395–425 (1968). MR 237962, DOI 10.1007/BF02590989
Gunnar Aronsson, On certain singular solutions of the partial differential equation $u^{2}_{x}u_{xx}+2u_{x}u_{y}u_{xy}+u^{2}_{y}u_{yy}=0$, Manuscripta Math. 47 (1984), no. 1-3, 133–151. MR 744316, DOI 10.1007/BF01174590
Gunnar Aronsson, Michael G. Crandall, and Petri Juutinen. A tour of the theory of absolutely minimizing functions. 65 pages, http:www.math.ucsb.edu/~crandall/paperdir/index.html, July 2003.
G. Barles and Jérôme Busca, Existence and comparison results for fully nonlinear degenerate elliptic equations without zeroth-order term, Comm. Partial Differential Equations 26 (2001), no. 11-12, 2323–2337. MR 1876420, DOI 10.1081/PDE-100107824
G. Barles and P. E. Souganidis, Convergence of approximation schemes for fully nonlinear second order equations, Asymptotic Anal. 4 (1991), no. 3, 271–283. MR 1115933
E. N. Barron, R. R. Jensen, and C. Y. Wang, The Euler equation and absolute minimizers of $L^\infty$ functionals, Arch. Ration. Mech. Anal. 157 (2001), no. 4, 255–283. MR 1831173, DOI 10.1007/PL00004239
E. N. Barron, R. R. Jensen, and C. Y. Wang, Lower semicontinuity of $L^\infty$ functionals, Ann. Inst. H. Poincaré C Anal. Non Linéaire 18 (2001), no. 4, 495–517 (English, with English and French summaries). MR 1841130, DOI 10.1016/S0294-1449(01)00070-1
Josep R. Casas and Luis Torres. Strong edge features for image coding, pages 443–450. Kluwer, Boston, MA, May 1996. R.W. Schafer, P. Maragos, and M.A. Butt, Eds. http:citeseer.nj.nec.com/113454.html.
Vicent Caselles, Jean-Michel Morel, and Catalina Sbert, An axiomatic approach to image interpolation, IEEE Trans. Image Process. 7 (1998), no. 3, 376–386. MR 1669524, DOI 10.1109/83.661188
M. G. Crandall, L. C. Evans, and R. F. Gariepy, Optimal Lipschitz extensions and the infinity Laplacian, Calc. Var. Partial Differential Equations 13 (2001), no. 2, 123–139. MR 1861094, DOI 10.1007/s005260000065
Michael G. Crandall, Hitoshi Ishii, and Pierre-Louis Lions, User’s guide to viscosity solutions of second order partial differential equations, Bull. Amer. Math. Soc. (N.S.) 27 (1992), no. 1, 1–67. MR 1118699, DOI 10.1090/S0273-0979-1992-00266-5
L. C. Evans and W. Gangbo, Differential equations methods for the Monge-Kantorovich mass transfer problem, Mem. Amer. Math. Soc. 137 (1999), no. 653, viii+66. MR 1464149, DOI 10.1090/memo/0653
Lawrence C. Evans. Personal communication.
Robert Jensen, Uniqueness of Lipschitz extensions: minimizing the sup norm of the gradient, Arch. Rational Mech. Anal. 123 (1993), no. 1, 51–74. MR 1218686, DOI 10.1007/BF00386368
Edward James McShane. Extension of range of functions. Bull. Amer. Math. Soc., 40:837–842, 1934.
Adam M. Oberman. Convergent difference schemes for degenerate elliptic and parabolic equations: Hamilton-Jacobi equations and free boundary problems. http:www.math. utexas.edu/~oberman, 2003.
Gilbert Strang, $L^{1}$ and $L^{\infty }$ approximation of vector fields in the plane, Nonlinear partial differential equations in applied science (Tokyo, 1982) North-Holland Math. Stud., vol. 81, North-Holland, Amsterdam, 1983, pp. 273–288. MR 730248
Hassler Whitney. Analytic extensions of differentiable functions defined in closed sets. Trans. Amer. Math. Soc., 36(1):63–89, 1934.