Mathematics of Computation

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

Author(s): Adam M. Oberman.
Journal: Math. Comp. 74 (2005), 1217-1230.
MSC (2000): Primary 35B50, 35J60, 35J70, 65N06, 65N12
Posted: September 10, 2004
Retrieve article in: PDF

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.

1.: 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(3):199-257, 1993. MR 94j:68306
2.: Gunnar Aronsson. Extension of functions satisfying Lipschitz conditions. Ark. Mat., 6:551-561 (1967), 1967. MR 36:754
3.: Gunnar Aronsson. On the partial differential equation $u\sb{x}{}\sp{2}u\sb{xx} +2u\sb{x}u\sb{y}u\sb{xy}+u\sb{y}{}\sp{2}u\sb{yy}=0$ . Ark. Mat., 7:395-425 (1968), 1968. MR 38:6239
4.: Gunnar Aronsson. On certain singular solutions of the partial differential equation $u\sp{2}\sb{x}u\sb{xx}+2u\sb{x}u\sb{y}u\sb{xy}+u\sp{2}\sb{y}u\sb{yy}=0$ . Manuscripta Math., 47(1-3):133-151, 1984. MR 85m:35011
5.: 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.
6.: Guy 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(11-12):2323-2337, 2001. MR 2002k:35078
7.: Guy Barles and Panagiotis E. Souganidis. Convergence of approximation schemes for fully nonlinear second order equations. Asymptotic Anal., 4(3):271-283, 1991. MR 92d:35137
8.: Emmanuel N. Barron, Robert R. Jensen, and Changyou Wang. The Euler equation and absolute minimizers of $L\sp \infty$ functionals. Arch. Ration. Mech. Anal., 157(4):255-283, 2001. MR 2002m:49006
9.: Emmanuel N. Barron, Robert R. Jensen, and Changyou Wang. Lower semicontinuity of $L\sp \infty$ functionals. Ann. Inst. H. Poincaré Anal. Non Linéaire, 18(4):495-517, 2001. MR 2002c:49020
10.: 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.
11.: Vicent Caselles, Jean-Michel Morel, and Catalina Sbert. An axiomatic approach to image interpolation. IEEE Trans. Image Process., 7(3):376-386, 1998. MR 2000d:94001
12.: M. G. Crandall, Lawrence C. Evans, and R. F. Gariepy. Optimal Lipschitz extensions and the infinity Laplacian. Calc. Var. Partial Differential Equations, 13(2):123-139, 2001.MR 2002h:49048
13.: 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(1):1-67, 1992. MR 92j:35050
14.: Lawrence C. Evans and Wilfrid Gangbo. Differential equations methods for the Monge-Kantorovich mass transfer problem. Mem. Amer. Math. Soc., 137(653):viii+66, 1999. MR 99g:35132
15.: Lawrence C. Evans. Personal communication.
16.: Robert Jensen. Uniqueness of Lipschitz extensions: minimizing the sup norm of the gradient. Arch. Rational Mech. Anal., 123(1):51-74, 1993. MR 94g:35063
17.: Edward James McShane. Extension of range of functions. Bull. Amer. Math. Soc., 40:837-842, 1934.
18.: 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.
19.: Gilbert Strang. $L\sp{1}$ and $L\sp{\infty }$ approximation of vector fields in the plane. In Nonlinear partial differential equations in applied science (Tokyo, 1982), volume 81 of North-Holland Math. Stud., pages 273-288. North-Holland, Amsterdam, 1983. MR 85c:49010
20.: Hassler Whitney. Analytic extensions of differentiable functions defined in closed sets. Trans. Amer. Math. Soc., 36(1):63-89, 1934.

Adam M. Oberman
Affiliation: Department of Mathematics, Simon Fraser University, 8888 University Dr., Burnaby, British Columbia Canada V5A 1S6
Email: aoberman@sfu.ca

DOI: 10.1090/S0025-5718-04-01688-6
PII: S 0025-5718(04)01688-6
Keywords: Finite difference, infinity Laplacian, viscosity solution
Received by editor(s): September 30, 2003
Received by editor(s) in revised form: December 29, 2003
Posted: September 10, 2004
Additional Notes: The author would like to thank P. E. Souganidis and A. Petrosyan for valuable discussions and L. C. Evans for his encouragement and enthusiasm.
Copyright of article: Copyright 2004, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS