Lipschitz maps

TheInfoList

OR:

In
mathematical analysis Analysis is the branch of mathematics dealing with continuous functions, limit (mathematics), limits, and related theories, such as Derivative, differentiation, Integral, integration, measure (mathematics), measure, infinite sequences, series (m ...
, Lipschitz continuity, named after German
mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, mathematical structure, structure, space, Mathematica ...
Rudolf Lipschitz, is a strong form of
uniform continuity In mathematics, a real function (mathematics), function f of real numbers is said to be uniformly continuous if there is a positive real number \delta such that function values over any function domain interval of the size \delta are as close to ea ...
for functions. Intuitively, a Lipschitz
continuous function In mathematics, a continuous function is a function (mathematics), function such that a continuous variation (that is a change without jump) of the argument of a function, argument induces a continuous variation of the Value (mathematics), value ...
is limited in how fast it can change: there exists a real number such that, for every pair of points on the graph of this function, the
absolute value In mathematics, the absolute value or modulus of a real number x, is the non-negative value without regard to its sign (mathematics), sign. Namely, , x, =x if is a positive number, and , x, =-x if x is negative number, negative (in which cas ...
of the slope of the line connecting them is not greater than this real number; the smallest such bound is called the ''Lipschitz constant'' of the function (or '' modulus of uniform continuity''). For instance, every function that has bounded first derivatives is Lipschitz continuous. In the theory of
differential equation In mathematics, a differential equation is an functional equation, equation that relates one or more unknown function (mathematics), functions and their derivatives. In applications, the functions generally represent physical quantities, the der ...
s, Lipschitz continuity is the central condition of the Picard–Lindelöf theorem which guarantees the existence and uniqueness of the solution to an
initial value problem In multivariable calculus, an initial value problem (IVP) is an ordinary differential equation together with an initial condition which specifies the value of the unknown function (mathematics), function at a given point in the domain of a functio ...
. A special type of Lipschitz continuity, called
contraction Contraction may refer to: Linguistics * Contraction (grammar), a shortened word * Poetic contraction, omission of letters for poetic reasons * Elision, omission of sounds ** Syncope (phonology), omission of sounds in a word * Synalepha, merged ...
, is used in the
Banach fixed-point theorem In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in mod ...
. We have the following chain of strict inclusions for functions over a closed and bounded non-trivial interval of the real line: :
Continuously differentiable In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in mo ...
⊂ Lipschitz continuous ⊂ $\alpha$- Hölder continuous, where $0 < \alpha \leq 1$. We also have : Lipschitz continuous ⊂
absolutely continuous In calculus, absolute continuity is a smoothness (mathematics), smoothness property of function (mathematics), functions that is stronger than continuous function, continuity and uniform continuity. The notion of absolute continuity allows one to o ...
uniformly continuous In mathematics, a real function (mathematics), function f of real numbers is said to be uniformly continuous if there is a positive real number \delta such that function values over any function domain interval of the size \delta are as close to ea ...
.

# Definitions

Given two
metric space In mathematics, a metric space is a Set (mathematics), set together with a notion of ''distance'' between its Element (mathematics), elements, usually called point (geometry), points. The distance is measured by a function (mathematics), functio ...
s (''X'', ''d''''X'') and (''Y'', ''d''''Y''), where ''d''''X'' denotes the
metric Metric or metrical may refer to: * Metric system, an internationally adopted decimal system of measurement * An adjective indicating relation to measurement in general, or a noun describing a specific type of measurement Mathematics In mathema ...
on the set ''X'' and ''d''''Y'' is the metric on set ''Y'', a function ''f'' : ''X'' → ''Y'' is called Lipschitz continuous if there exists a real constant ''K'' ≥ 0 such that, for all ''x''1 and ''x''2 in ''X'', :$d_Y\left(f\left(x_1\right), f\left(x_2\right)\right) \le K d_X\left(x_1, x_2\right).$ Any such ''K'' is referred to as a Lipschitz constant for the function ''f'' and ''f'' may also be referred to as K-Lipschitz. The smallest constant is sometimes called the (best) Lipschitz constant of ''f'' or the dilation or dilatation of ''f''. If ''K'' = 1 the function is called a
short map In the mathematics, mathematical theory of metric spaces, a metric map is a Function (mathematics), function between metric spaces that does not increase any distance (such functions are always continuous function, continuous). These maps are the m ...
, and if 0 ≤ ''K'' < 1 and ''f'' maps a metric space to itself, the function is called a
contraction Contraction may refer to: Linguistics * Contraction (grammar), a shortened word * Poetic contraction, omission of letters for poetic reasons * Elision, omission of sounds ** Syncope (phonology), omission of sounds in a word * Synalepha, merged ...
. In particular, a
real-valued function In mathematics, a real-valued function is a function whose values are real number In mathematics, a real number is a number that can be used to measurement, measure a ''continuous'' one-dimensional quantity such as a distance, time, durati ...
''f'' : ''R'' → ''R'' is called Lipschitz continuous if there exists a positive real constant K such that, for all real ''x''1 and ''x''2, :$, f\left(x_1\right) - f\left(x_2\right), \le K , x_1 - x_2, .$ In this case, ''Y'' is the set of
real number In mathematics, a real number is a number that can be used to measurement, measure a ''continuous'' one-dimensional quantity such as a distance, time, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small var ...
s R with the standard metric ''d''''Y''(''y1'', ''y2'') = , ''y1'' − ''y2'', , and ''X'' is a subset of R. In general, the inequality is (trivially) satisfied if ''x''1 = ''x''2. Otherwise, one can equivalently define a function to be Lipschitz continuous
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bicondi ...
there exists a constant ''K'' ≥ 0 such that, for all ''x''1 ≠ ''x''2, :$\frac\le K.$ For real-valued functions of several real variables, this holds if and only if the absolute value of the slopes of all secant lines are bounded by ''K''. The set of lines of slope ''K'' passing through a point on the graph of the function forms a circular cone, and a function is Lipschitz if and only if the graph of the function everywhere lies completely outside of this cone (see figure). A function is called locally Lipschitz continuous if for every ''x'' in ''X'' there exists a
neighborhood A neighbourhood (British English British English (BrE, en-GB, or BE) is, according to Oxford Dictionaries, " English as used in Great Britain, as distinct from that used elsewhere". More narrowly, it can refer specifically to the En ...
''U'' of ''x'' such that ''f'' restricted to ''U'' is Lipschitz continuous. Equivalently, if ''X'' is a
locally compact In topology and related branches of mathematics, a topological space is called locally compact if, roughly speaking, each small portion of the space looks like a small portion of a compact space. More precisely, it is a topological space in which ev ...
metric space, then ''f'' is locally Lipschitz if and only if it is Lipschitz continuous on every compact subset of ''X''. In spaces that are not locally compact, this is a necessary but not a sufficient condition. More generally, a function ''f'' defined on ''X'' is said to be Hölder continuous or to satisfy a Hölder condition of order α > 0 on ''X'' if there exists a constant ''M'' ≥ 0 such that :$d_Y\left(f\left(x\right), f\left(y\right)\right) \leq M d_X\left(x, y\right)^$ for all ''x'' and ''y'' in ''X''. Sometimes a Hölder condition of order α is also called a uniform Lipschitz condition of order α > 0. For a real number ''K'' ≥ 1, if :$\fracd_X\left(x_1,x_2\right) \le d_Y\left(f\left(x_1\right), f\left(x_2\right)\right) \le K d_X\left(x_1, x_2\right)\quad\textx_1,x_2\in X,$ then ''f'' is called ''K''-bilipschitz (also written ''K''-bi-Lipschitz). We say ''f'' is bilipschitz or bi-Lipschitz to mean there exists such a ''K''. A bilipschitz mapping is
injective In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in ...
, and is in fact a
homeomorphism In the mathematics, mathematical field of topology, a homeomorphism, topological isomorphism, or bicontinuous function is a bijective and Continuous function#Continuous functions between topological spaces, continuous function between topologic ...
onto its image. A bilipschitz function is the same thing as an injective Lipschitz function whose
inverse function In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in ...
is also Lipschitz.

# Examples

;Lipschitz continuous functions: ;Lipschitz continuous functions that are not everywhere differentiable: ;Lipschitz continuous functions that are everywhere differentiable but not continuously differentiable: ;Continuous functions that are not (globally) Lipschitz continuous: ;Differentiable functions that are not (locally) Lipschitz continuous: ;Analytic functions that are not (globally) Lipschitz continuous:

# Properties

*An everywhere differentiable function ''g'' : R → R is Lipschitz continuous (with ''K'' = sup , ''g''′(''x''), ) if and only if it has bounded
first derivative In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented ...
; one direction follows from the
mean value theorem In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in ...
. In particular, any continuously differentiable function is locally Lipschitz, as continuous functions are locally bounded so its gradient is locally bounded as well. *A Lipschitz function ''g'' : R → R is
absolutely continuous In calculus, absolute continuity is a smoothness (mathematics), smoothness property of function (mathematics), functions that is stronger than continuous function, continuity and uniform continuity. The notion of absolute continuity allows one to o ...
and therefore is differentiable
almost everywhere In measure theory (a branch of mathematical analysis Analysis is the branch of mathematics dealing with continuous functions, limit (mathematics), limits, and related theories, such as Derivative, differentiation, Integral, integration, meas ...
, that is, differentiable at every point outside a set of
Lebesgue measure In Measure (mathematics), measure theory, a branch of mathematics, the Lebesgue measure, named after france, French mathematician Henri Lebesgue, is the standard way of assigning a measure (mathematics), measure to subsets of ''n''-dimensional Eucl ...
zero. Its derivative is
essentially bounded Essence ( la, essentia) is a polysemic term, used in philosophy Philosophy (from , ) is the systematized study of general and fundamental questions, such as those about existence, reason, knowledge, values, mind, and language. Such ...
in magnitude by the Lipschitz constant, and for ''a'' < ''b'', the difference ''g''(''b'') − ''g''(''a'') is equal to the integral of the derivative ''g''′ on the interval 'a'', ''b'' **Conversely, if ''f'' : ''I'' → R is absolutely continuous and thus differentiable almost everywhere, and satisfies , ''f′''(''x''),  ≤ ''K'' for almost all ''x'' in ''I'', then ''f'' is Lipschitz continuous with Lipschitz constant at most ''K''. **More generally,
Rademacher's theorem In mathematical analysis Analysis is the branch of mathematics dealing with continuous functions, limit (mathematics), limits, and related theories, such as Derivative, differentiation, Integral, integration, measure (mathematics), measure, infi ...
extends the differentiability result to Lipschitz mappings between Euclidean spaces: a Lipschitz map ''f'' : ''U'' → R''m'', where ''U'' is an open set in R''n'', is
almost everywhere In measure theory (a branch of mathematical analysis Analysis is the branch of mathematics dealing with continuous functions, limit (mathematics), limits, and related theories, such as Derivative, differentiation, Integral, integration, meas ...
differentiable In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in mo ...
. Moreover, if ''K'' is the best Lipschitz constant of ''f'', then $\, Df\left(x\right)\, \le K$ whenever the
total derivative In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in ...
''Df'' exists. *For a differentiable Lipschitz map $f: U \to \R^m$ the inequality $\, Df\, _\le K$ holds for the best Lipschitz constant $K$ of $f$. If the domain $U$ is convex then in fact $\, Df\, _= K$. *Suppose that is a sequence of Lipschitz continuous mappings between two metric spaces, and that all ''fn'' have Lipschitz constant bounded by some ''K''. If ''fn'' converges to a mapping ''f'' uniformly, then ''f'' is also Lipschitz, with Lipschitz constant bounded by the same ''K''. In particular, this implies that the set of real-valued functions on a compact metric space with a particular bound for the Lipschitz constant is a closed and convex subset of the
Banach space In mathematics, more specifically in functional analysis, a Banach space (pronounced ) is a Complete metric space, complete normed vector space. Thus, a Banach space is a vector space with a Metric (mathematics), metric that allows the computation ...
of continuous functions. This result does not hold for sequences in which the functions may have ''unbounded'' Lipschitz constants, however. In fact, the space of all Lipschitz functions on a compact metric space is a subalgebra of the Banach space of continuous functions, and thus dense in it, an elementary consequence of the
Stone–Weierstrass theorem In mathematical analysis Analysis is the branch of mathematics dealing with continuous functions, limit (mathematics), limits, and related theories, such as Derivative, differentiation, Integral, integration, measure (mathematics), measure, inf ...
(or as a consequence of
Weierstrass approximation theorem Karl Theodor Wilhelm Weierstrass (german: link=no, Weierstraß ; 31 October 1815 – 19 February 1897) was a German mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve ma ...
, because every polynomial is locally Lipschitz continuous). *Every Lipschitz continuous map is
uniformly continuous In mathematics, a real function (mathematics), function f of real numbers is said to be uniformly continuous if there is a positive real number \delta such that function values over any function domain interval of the size \delta are as close to ea ...
, and hence '' a fortiori'' continuous. More generally, a set of functions with bounded Lipschitz constant forms an
equicontinuous In mathematical analysis, a family of functions is equicontinuous if all the functions are continuous function, continuous and they have equal variation over a given neighbourhood (mathematics), neighbourhood, in a precise sense described herein. ...
set. The
Arzelà–Ascoli theorem The Arzelà–Ascoli theorem is a fundamental result of mathematical analysis giving necessary and sufficient conditions to decide whether every sequence (mathematics), sequence of a given family of real number, real-valued continuous functions def ...
implies that if is a
uniformly bounded In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in mod ...
sequence of functions with bounded Lipschitz constant, then it has a convergent subsequence. By the result of the previous paragraph, the limit function is also Lipschitz, with the same bound for the Lipschitz constant. In particular the set of all real-valued Lipschitz functions on a compact metric space ''X'' having Lipschitz constant ≤ ''K''  is a
locally compact In topology and related branches of mathematics, a topological space is called locally compact if, roughly speaking, each small portion of the space looks like a small portion of a compact space. More precisely, it is a topological space in which ev ...
convex subset of the Banach space ''C''(''X''). *For a family of Lipschitz continuous functions ''f''α with common constant, the function $\sup_\alpha f_\alpha$ (and $\inf_\alpha f_\alpha$) is Lipschitz continuous as well, with the same Lipschitz constant, provided it assumes a finite value at least at a point. *If ''U'' is a subset of the metric space ''M'' and ''f'' : ''U'' → R is a Lipschitz continuous function, there always exist Lipschitz continuous maps ''M'' → R which extend ''f'' and have the same Lipschitz constant as ''f'' (see also Kirszbraun theorem). An extension is provided by ::$\tilde f\left(x\right):=\inf_\,$ :where ''k'' is a Lipschitz constant for ''f'' on ''U''.

# Lipschitz manifolds

A Lipschitz structure on a
topological manifold In topology, a branch of mathematics, a topological manifold is a topological space that locally resembles real numbers, real ''n''-dimension (mathematics), dimensional Euclidean space. Topological manifolds are an important class of topological spa ...
is defined using an atlas of charts whose transition maps are bilipschitz; this is possible because bilipschitz maps form a
pseudogroup In mathematics, a pseudogroup is a set of diffeomorphisms between open sets of a space, satisfying group-like and sheaf-like properties. It is a generalisation of the concept of a group (mathematics), group, originating however from the geometric ap ...
. Such a structure allows one to define locally Lipschitz maps between such manifolds, similarly to how one defines smooth maps between
smooth manifold In mathematics, a differentiable manifold (also differential manifold) is a type of manifold In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spa ...
s: if and are Lipschitz manifolds, then a function $f:M \to N$ is locally Lipschitz if and only if for every pair of coordinate charts $\phi:U \to M$ and $\psi:V \to N$, where and are open sets in the corresponding Euclidean spaces, the composition $\psi^ \circ f \circ \phi:U \cap (f \circ \phi)^(\psi(V)) \to N$ is locally Lipschitz. This definition does not rely on defining a metric on or . This structure is intermediate between that of a piecewise-linear manifold and a
topological manifold In topology, a branch of mathematics, a topological manifold is a topological space that locally resembles real numbers, real ''n''-dimension (mathematics), dimensional Euclidean space. Topological manifolds are an important class of topological spa ...
: a PL structure gives rise to a unique Lipschitz structure. While Lipschitz manifolds are closely related to topological manifolds,
Rademacher's theorem In mathematical analysis Analysis is the branch of mathematics dealing with continuous functions, limit (mathematics), limits, and related theories, such as Derivative, differentiation, Integral, integration, measure (mathematics), measure, infi ...
allows one to do analysis, yielding various applications.

# One-sided Lipschitz

Let ''F''(''x'') be an upper semi-continuous function of ''x'', and that ''F''(''x'') is a closed, convex set for all ''x''. Then ''F'' is one-sided Lipschitz if :$\left(x_1-x_2\right)^T\left(F\left(x_1\right)-F\left(x_2\right)\right)\leq C\Vert x_1-x_2\Vert^2$ for some ''C'' and for all ''x''1 and ''x''2. It is possible that the function ''F'' could have a very large Lipschitz constant but a moderately sized, or even negative, one-sided Lipschitz constant. For example, the function :$\begin F:\mathbf^2\to\mathbf,\\ F\left(x,y\right)=-50\left(y-\cos\left(x\right)\right) \end$ has Lipschitz constant ''K'' = 50 and a one-sided Lipschitz constant ''C'' = 0. An example which is one-sided Lipschitz but not Lipschitz continuous is ''F''(''x'') = ''e''−''x'', with ''C'' = 0.

* * Dini continuity * Modulus of continuity * Quasi-isometry * Johnson-Lindenstrauss lemma – For any integer ''n''≥0, any finite subset ''X''⊆''Rn'', and any real number 0<ε<1, there exists a (1+ε)-bi-Lipschitz function $f:\mathbb R^n\to\mathbb R^d,$ where $d=\lceil15\left(\ln, X, \right)/\varepsilon^2\rceil.$