Gradient Flows · Study tools

InteractiveAmbrosio–Gigli–Savaré, Ch. 1: Curves and Gradients in Metric Spaces

Curves of maximal slope

In $\R^d$ a gradient flow is $u'=-\nabla\varphi(u)$ , an equation between vectors. A metric space has no vectors, but it still has speeds and slopes. The surprise is that one scalar inequality between speed, slope and energy already contains the whole equation.

The idea

Metric derivative. A curve

u:(a,b)\to S

in a metric space

(S,d)

is absolutely continuous if

d(u(s),u(t))\le\int_s^t m(r)\,dr

for some

m\in L^1(a,b)

and all

s<t

. For such curves the limit

|u'|(t)=\lim_{h\to0}\frac{d(u(t+h),u(t))}{|h|}

exists for almost every

t

, and it is the smallest admissible

m

. It is the speed of the curve; there is no velocity vector.

Local slope. For

\varphi:S\to(-\infty,+\infty]

and

v

with

\varphi(v)<\infty

,

|\partial\varphi|(v)=\limsup_{w\to v}\frac{\big(\varphi(v)-\varphi(w)\big)^+}{d(v,w)}.

It is the steepest rate of descent from

v

. For a

C^1

function on

\R^d

it equals

|\nabla\varphi(v)|

, but it needs no differentiability.

In $\R^d$ , the chain rule and two elementary inequalities give, along any smooth curve,

-\frac{d}{dt}\varphi(u) = -\langle\nabla\varphi(u),u'\rangle \le |\nabla\varphi(u)|\,|u'| \le \tfrac12|u'|^2+\tfrac12|\nabla\varphi(u)|^2 .

Equality in Cauchy–Schwarz forces $u'$ to point along $-\nabla\varphi$ ; equality in Young's inequality forces $|u'|=|\nabla\varphi|$ . Together: $u'=-\nabla\varphi(u)$ . So the gradient flow is exactly the curve that makes the energy fall as fast as this bound allows.

Curve of maximal slope. An absolutely continuous

u

along which

\varphi\circ u

is nonincreasing and

\varphi(u(s))-\varphi(u(t)) \ \ge\ \frac12\int_s^t|u'|^2(r)\,dr+\frac12\int_s^t|\partial\varphi|^2(u(r))\,dr \qquad(s\le t).

(Ch. 1 allows any upper gradient

g

in place of

|\partial\varphi|

.)

Energy dissipation equality. If the slope is a strong upper gradient, meaning

|\varphi(u(t))-\varphi(u(s))|\le\int_s^t|\partial\varphi|(u)\,|u'|\,dr

along every absolutely continuous curve, then the inequality above is automatically an equality. For

\varphi\in C^1(\R^d)

, curves of maximal slope are exactly the solutions of

u'=-\nabla\varphi(u)

.

Below, the curve follows $u'=\alpha R_\theta(-\nabla\varphi(u))$ : the true gradient flow sped up by $\alpha$ and turned by an angle $\theta$ . Compare the energy it loses with the right-hand side.

Explore

Energy φ

Speed factor α 1.00 Turn angle θ 0°

the curve

u

on

[0,T]

true gradient flow · drag the start point

energy lost

\varphi(u_0)-\varphi(u(t))

\tfrac12\int_0^t|u'|^2+\tfrac12\int_0^t|\nabla\varphi(u)|^2

Worked example

Take $S=\R$ and the nonsmooth energy $\varphi(x)=|x|$ . Which curves starting at $u_0=1$ are curves of maximal slope?

Compute the local slope $|\partial\varphi|(x)$ at every $x$ , including $x=0$ .

For $x\neq0$ , $\varphi$ is differentiable with $|\varphi'(x)|=1$ , so the slope is 1. At $x=0$ : $\big(\varphi(0)-\varphi(w)\big)^+=(-|w|)^+=0$ for every $w$ , so $|\partial\varphi|(0)=0$ . The minimum has slope zero even though $\varphi$ has a corner there.
Check that $u(t)=(1-t)^+$ satisfies the energy inequality on $[0,t]$ , first for $t\le1$ and then for $t>1$ .

For $t\le1$ : energy lost $=1-(1-t)=t$ ; speed 1 and slope 1 give $\tfrac12 t+\tfrac12 t=t$ . Equality.

For $t>1$ : energy lost $=1$ ; the integrals are $\tfrac12\cdot1+\tfrac12\cdot1=1$ , because after time 1 both speed and slope are zero. Equality again.
Try the curve that moves twice as fast, $u(t)=(1-2t)^+$ , on $[0,\tfrac12]$ .

Energy lost $=1$ . Right side: $\tfrac12\int_0^{1/2}4\,dr+\tfrac12\int_0^{1/2}1\,dr=1+\tfrac14=\tfrac54>1$ . The inequality fails: going faster costs more in $\tfrac12|u'|^2$ than it gains in energy.
What about the curve that never moves, $u\equiv1$ ?

Energy lost $=0$ , but the slope term is $\tfrac12\int_0^t1\,dr=t/2>0$ . It fails too. The slope term is what forces the curve to move; the speed term is what stops it moving too fast. Only $(1-t)^+$ balances them, and it is exactly the solution of the differential inclusion $u'\in-\partial|u|$ .

Check your understanding

Give $\R^2$ the $\ell^1$ distance $d(x,y)=|x_1-y_1|+|x_2-y_2|$ . What is the metric derivative of $u(t)=(t,t)$ ?

$\sqrt2$ That is the Euclidean speed. The metric derivative is computed with the distance you are given.
$2$
$1$ Each coordinate moves at speed 1, and the $\ell^1$ distance adds the two.

d(u(t+h),u(t))=|h|+|h|=2|h|

, so

|u'|(t)=2

. Speeds, and so curves of maximal slope, depend on the metric. In Part II the metric will be the Wasserstein distance, and changing the metric is exactly what turns one PDE into another.

In $\R^d$ , a curve satisfies $\varphi(u(s))-\varphi(u(t))=\int_s^t|u'|\,|\nabla\varphi(u)|\,dr$ for all $s\le t$ (speed times slope, instead of the two half-squares). Must it solve $u'=-\nabla\varphi(u)$ ?

Yes, this is the energy identity.Try $u'=-2\nabla\varphi(u)$ : the energy falls at rate $2|\nabla\varphi|^2=|u'|\,|\nabla\varphi|$ .
No. It forces $u'$ to point along $-\nabla\varphi$ , but not the speed.
No. It does not even fix the direction.Equality in Cauchy–Schwarz, $-\langle\nabla\varphi,u'\rangle=|\nabla\varphi||u'|$ , does force $u'$ to be a nonnegative multiple of $-\nabla\varphi$ .

Any reparametrisation of a gradient-flow trajectory passes this test. Replacing

|u'||\nabla\varphi|

by

\tfrac12|u'|^2+\tfrac12|\nabla\varphi|^2

adds equality in Young's inequality,

|u'|=|\nabla\varphi|

, which fixes the speed. In the explorer,

\alpha\neq1

with

\theta=0

is exactly this situation.

On $\R$ , let $\varphi(x)=-|x|$ . What is $|\partial\varphi|(0)$ ?

$0$ , since $0$ is a critical point.The slope measures descent. From $0$ you can go down at rate 1 in either direction.
$1$
Undefined, since $\varphi$ is not differentiable at 0.The slope is a limsup of difference quotients and is defined at every point of the domain.

\big(\varphi(0)-\varphi(w)\big)^+/|w|=|w|/|w|=1

. So the constant curve at

0

is not a curve of maximal slope (it loses no energy but pays

\tfrac12\int 1

). Curves of maximal slope from

0

leave at speed 1, to the left or to the right: they exist, but they are not unique. Uniqueness needs convexity, which is the subject of Chapter 4.

Practice

The inequality implies the equationThe smooth case in

\R^d

Let $\varphi\in C^1(\R^d)$ and let $u$ be absolutely continuous on $[0,T]$ with $\varphi(u(0))-\varphi(u(T))\ge\tfrac12\int_0^T|u'|^2+\tfrac12\int_0^T|\nabla\varphi(u)|^2$ . Show that $u'=-\nabla\varphi(u)$ almost everywhere.

Hint

Write $\varphi(u(0))-\varphi(u(T))=-\int_0^T\langle\nabla\varphi(u),u'\rangle\,dt$ and compare integrands.

Solution

A space with no moving curvesThe snowflake metric

On $\R$ put $d(x,y)=|x-y|^{1/2}$ . Show that every absolutely continuous curve $u:[a,b]\to(\R,d)$ is constant. What does that say about gradient flows in this space?

Hint

From $|u(t)-u(s)|^{1/2}\le\int_s^t m$ , get $|u(t)-u(s)|\le\big(\int_s^tm\big)^2$ , and sum over a fine partition.

Solution

Split $[a,b]$ into intervals $I_k$ . Then

|u(b)-u(a)|\le\sum_k\Big(\int_{I_k}m\Big)^2\le\Big(\max_k\int_{I_k}m\Big)\int_a^bm,

and the maximum tends to 0 as the mesh shrinks, since

m\in L^1

. So

u(b)=u(a)

, and likewise on every subinterval. The only curves of maximal slope are constants, at points of zero slope. A metric theory of gradient flows needs a space with many rectifiable curves; the Wasserstein space will have plenty.

InteractiveAmbrosio–Gigli–Savaré, Ch. 2: Existence of Curves of Maximal Slope and their Variational Approximation

Minimizing movements

To build a gradient flow where there are no gradients, take small steps, each of which lowers the energy without moving too far. This is implicit Euler written as a minimization problem, and it makes sense in any metric space.

The idea

One step. For a step size

\tau>0

and a point

u

, minimize

\Phi(\tau,u;v)=\varphi(v)+\frac{d^2(u,v)}{2\tau}.

A discrete solution starts at

U^0=u_0

and picks

U^n

among the minimizers of

\Phi(\tau,U^{n-1};\cdot)

. Interpolating piecewise constantly in time gives a curve

\bar U_\tau

.

Minimizing movement. A curve

u

is a generalized minimizing movement if

\bar U_{\tau_k}(t)\to u(t)

for some sequence

\tau_k\downarrow0

and every

t

. ("Generalized" because the minimizers, and the limits, need not be unique.)

In $\R^d$ with smooth $\varphi$ the minimizer satisfies $\dfrac{U^n-U^{n-1}}{\tau}=-\nabla\varphi(U^n)$ : this is implicit Euler. For convex nonsmooth $\varphi$ it reads $\dfrac{U^{n-1}-U^n}{\tau}\in\partial\varphi(U^n)$ . Comparing with $v=U^{n-1}$ gives, for free, the discrete energy inequality

\varphi(U^n)+\frac{d^2(U^n,U^{n-1})}{2\tau}\le\varphi(U^{n-1}).

Existence (Ch. 2). If

\varphi

is lower semicontinuous, bounded below on bounded sets in a suitable sense, and its sublevels are (relatively) compact, then discrete solutions exist and generalized minimizing movements exist. If moreover the relaxed slope

|\partial^-\varphi|

(a lower semicontinuous relaxation of

|\partial\varphi|

) is a strong upper gradient, every one of them is a curve of maximal slope for it and satisfies the energy dissipation equality (Theorem 2.3.3; Theorem 2.3.1 reaches the same conclusion, without the equality, from a weaker chain rule plus a continuity condition on

\varphi

).

The convex case. If

\varphi

is

\lambda

-convex along geodesics, the slope is lower semicontinuous and a strong upper gradient, so the theorem applies directly. Chapter 4 adds uniqueness and error bounds, under a slightly stronger convexity assumption (Module 4) that holds, for instance, in Hilbert spaces; for

\lambda\ge0

,

d(U^N,u(N\tau))\le\tau\,|\partial\varphi|(u_0)/\sqrt2

.

Explicit Euler is not an option.

U^n=U^{n-1}-\tau\nabla\varphi(U^{n-1})

needs a vector to step along, and even in

\R

it is unstable for stiff or nonsmooth

\varphi

. The explorer runs both.

Explore

Energy φ

Step τ 0.30

minimizing movement explicit Euler · dashed:

\Phi(\tau,U^0;\cdot)

· drag

u_0

exact gradient flow

U^n

explicit, against time

t=n\tau

Worked example

Run the minimizing-movement scheme for $\varphi(x)=|x|$ on $\R$ from $u_0=1$ , and compare it with explicit Euler using the subgradient $\operatorname{sign}(x)$ .

Solve one step: minimize $|v|+\dfrac{(v-a)^2}{2\tau}$ for given $a>0$ .

The optimality condition is $\dfrac{a-v}{\tau}\in\partial|v|$ . If $v>0$ this says $v=a-\tau$ , which is consistent when $a>\tau$ . If $v=0$ it says $a/\tau\in[-1,1]$ , i.e. $a\le\tau$ . So

$U^n=\max\big(U^{n-1}-\tau,\,0\big)\quad\text{(soft thresholding).}$
Write out $U^n$ from $u_0=1$ and compare it with the exact flow $u(t)=(1-t)^+$ from the previous module.

$U^n=(1-n\tau)^+=u(n\tau)$ . The scheme is exact at the grid times, and in particular it lands on the minimum and stays there.
Now explicit Euler with $\tau=0.3$ : $U^n=U^{n-1}-0.3\,\operatorname{sign}(U^{n-1})$ . What happens?

$1,\ 0.7,\ 0.4,\ 0.1,\ -0.2,\ 0.1,\ -0.2,\dots$ It never settles: it oscillates around the minimum with amplitude of order $\tau$ , and $\varphi(U^n)$ goes up on every other step.
Check the discrete energy inequality for the implicit step when $a>\tau$ .

$\varphi(U^n)+\dfrac{|U^n-a|^2}{2\tau}=(a-\tau)+\dfrac{\tau}{2}=a-\dfrac\tau2\le a=\varphi(a)$ . The energy drops by at least the "kinetic" term $d^2/2\tau$ , which is the discrete version of $\tfrac12\int|u'|^2$ .

Check your understanding

For $\varphi(x)=\tfrac12x^2$ on $\R$ , what is one minimizing-movement step from $x$ ?

$x/(1+\tau)$
$x(1-\tau)$ That is explicit Euler. Set the derivative of $\tfrac12v^2+(v-x)^2/2\tau$ to zero.
$x e^{-\tau}$ That is the exact flow after time $\tau$ , which the scheme only approximates.

v+(v-x)/\tau=0

gives

v=x/(1+\tau)

. After

n=t/\tau

steps,

x(1+t/n)^{-n}\to xe^{-t}

. Note

1/(1+\tau)\in(0,1)

for every

\tau>0

: the scheme never overshoots, unlike

1-\tau

, which overshoots for

\tau>1

and diverges for

\tau>2

.

Why is the minimizing-movement scheme, and not explicit Euler, the right starting point in a metric space?

It only uses $\varphi$ and $d$ ; there is no vector $-\nabla\varphi$ to step along.
It is more accurate.Both are first-order methods. The point is that one of them can be written down at all.
Its minimizer is always unique.Not for nonconvex $\varphi$ : see the next question. That is why the theory speaks of generalized minimizing movements.

\Phi(\tau,u;v)=\varphi(v)+d^2(u,v)/2\tau

is meaningful in any metric space. Its stability (the discrete energy inequality) also gives the compactness needed to pass to the limit, which is the content of Chapters 2 and 3.

Double well $\varphi(x)=\tfrac14(x^2-1)^2$ , start at $u_0=0$ (a local maximum), step $\tau=2$ . What is $U^1$ ?

$0$ , since $\varphi'(0)=0$ .Compare values: $\Phi(2,0;0)=\tfrac14$ , while $\Phi(2,0;1/\sqrt2)=\tfrac1{16}+\tfrac18=\tfrac3{16}$ .
Either $1/\sqrt2$ or $-1/\sqrt2$ : there are two minimizers and the scheme must choose.
$1$ , the bottom of a well.At $v=1$ , $\Phi=0+\tfrac14=\tfrac14$ , which is beaten by $v=1/\sqrt2$ .

The derivative of

\Phi

is

v(v^2-1+1/\tau)

. For

\tau<1

its only zero is

v=0

, and

\Phi

is convex, so the scheme stays at 0 like the exact flow. For

\tau>1

the minimizers are

\pm\sqrt{1-1/\tau}

. Try it in the explorer: drag

u_0

to 0 and move

\tau

across 1.

Practice

A discrete Hölder estimateWhere compactness comes from

Let $\varphi\ge\varphi_{\min}$ and $U^n$ be a discrete solution. Show that $\sum_n d^2(U^n,U^{n-1})\le2\tau\,(\varphi(u_0)-\varphi_{\min})$ , and deduce $d(U^m,U^n)\le\sqrt{2(\varphi(u_0)-\varphi_{\min})}\,\sqrt{|m-n|\tau}$ .

Hint

Sum the discrete energy inequality (it telescopes), then use Cauchy–Schwarz on $\sum_{k=n+1}^m d(U^k,U^{k-1})$ .

Solution

Summing $d^2(U^k,U^{k-1})/2\tau\le\varphi(U^{k-1})-\varphi(U^k)$ gives the first bound. Then

d(U^m,U^n)\le\sum_{k=n+1}^m d(U^k,U^{k-1})\le\sqrt{m-n}\,\Big(\sum_k d^2\Big)^{1/2}\le\sqrt{m-n}\,\sqrt{2\tau(\varphi(u_0)-\varphi_{\min})}.

Since

|m-n|\tau

is the time elapsed, the discrete curves are uniformly

\tfrac12

-Hölder, which (with compact sublevels) gives a convergent subsequence by an Arzelà–Ascoli argument.

A concave energyWhen does a step exist?

Let $\varphi(x)=-\tfrac12x^2$ on $\R$ . For which $\tau$ does $\Phi(\tau,a;\cdot)$ have a minimizer? Compute $U^n$ and its limit as $\tau=t/n\to0$ .

Solution

$\Phi=-\tfrac12v^2+(v-a)^2/2\tau$ has leading coefficient $\tfrac12(1/\tau-1)$ . It is bounded below, with the unique minimizer $v=a/(1-\tau)$ , exactly when $\tau<1$ ; for $\tau\ge1$ it is unbounded below (or, at $\tau=1$ with $a\neq0$ , linear). So $U^n=a(1-\tau)^{-n}\to ae^{t}$ , the exact flow of $u'=u$ . The restriction $\tau<1/(-\lambda)$ with $\lambda=-1$ is the one that appears for $\lambda$ -convex energies in Chapter 4.

InteractiveAmbrosio–Gigli–Savaré, Ch. 3: Proofs of the Convergence Theorems

The Moreau–Yosida envelope

The value of one minimizing-movement step, seen as a function of the starting point, is a smoothed version of the energy. How it changes with $\tau$ is the key to the convergence proof: it turns the discrete energy inequality into a discrete energy identity.

The idea

Moreau–Yosida approximation.

\varphi_\tau(u)=\inf_{v\in S}\Big(\varphi(v)+\frac{d^2(u,v)}{2\tau}\Big),

and

J_\tau[u]

is the set of minimizers

u_\tau

. Taking

v=u

shows

\varphi_\tau\le\varphi

; the penalty shrinks as

\tau

grows, so

\tau\mapsto\varphi_\tau(u)

is nonincreasing, and

\varphi_\tau(u)\uparrow\varphi(u)

as

\tau\downarrow0

when

\varphi

is lower semicontinuous (under the standing compactness assumptions).

The picture: lower the downward parabola $v\mapsto c-d^2(u,v)/2\tau$ until it touches the graph of $\varphi$ . The highest $c$ that stays below $\varphi$ is $\varphi_\tau(u)$ , and the touching points are $J_\tau[u]$ .

Derivative in $\tau$ . For almost every

\tau

,

\frac{d}{d\tau}\varphi_\tau(u)=-\frac{d^2(u,u_\tau)}{2\tau^2}.

Slope estimate. For every

u_\tau\in J_\tau[u]

,

|\partial\varphi|(u_\tau)\le\frac{d(u,u_\tau)}{\tau}.

In words: the endpoint of a step has slope at most the discrete speed of that step.

Integrate the derivative from $0$ to $\tau$ and use the slope estimate along the family $u_r\in J_r[u]$ , $0<r\le\tau$ (De Giorgi's variational interpolation). One step then satisfies

\varphi(u)-\varphi(u_\tau)=\frac{d^2(u,u_\tau)}{2\tau}+\int_0^\tau\frac{d^2(u,u_r)}{2r^2}\,dr\ \ge\ \frac{d^2(u,u_\tau)}{2\tau}+\frac12\int_0^\tau|\partial\varphi|^2(u_r)\,dr,

the discrete counterpart of the energy inequality of Module 1, with both the speed and the slope terms. Passing to the limit in it is the heart of Chapter 3.

Explore

Energy φ

τ 0.50

\varphi

\varphi_\tau

parabola touching at

u_\tau

· drag u

r\mapsto\varphi_r(u)

slope

-d^2(u,u_\tau)/2\tau^2

at

r=\tau

Worked example

Compute $J_\tau$ and $\varphi_\tau$ for $\varphi(x)=|x|$ on $\R$ , and check the derivative formula and the slope estimate by hand.

What is $J_\tau[x]$ ? (You solved this in the previous module.)

Soft thresholding: $x_\tau=\operatorname{sign}(x)\max(|x|-\tau,0)$ .
Compute $\varphi_\tau(x)$ .

If $|x|\le\tau$ , $x_\tau=0$ and $\varphi_\tau(x)=x^2/2\tau$ . If $|x|>\tau$ , $\varphi_\tau(x)=(|x|-\tau)+\tau^2/2\tau=|x|-\tau/2$ . This is the Huber function: a parabola near the corner, joined to two lines. It is $C^1$ with $\varphi_\tau'(x)=(x-x_\tau)/\tau$ .
Check $\dfrac{d}{d\tau}\varphi_\tau(x)=-\dfrac{|x-x_\tau|^2}{2\tau^2}$ in both regimes.

For $|x|>\tau$ : $\frac{d}{d\tau}(|x|-\tau/2)=-\tfrac12$ , and $|x-x_\tau|=\tau$ gives $-\tau^2/2\tau^2=-\tfrac12$ . For $|x|<\tau$ : $\frac{d}{d\tau}\,x^2/2\tau=-x^2/2\tau^2$ , and $|x-x_\tau|=|x|$ . Both match.
Check the slope estimate $|\partial\varphi|(x_\tau)\le|x-x_\tau|/\tau$ . When is it an equality?

For $|x|>\tau$ : slope at $x_\tau\neq0$ is 1, and $|x-x_\tau|/\tau=1$ . Equality. For $|x|\le\tau$ : $x_\tau=0$ has slope 0, while $|x|/\tau$ can be up to 1. Strict inequality (unless $|x|=\tau$ ). The step ends at a point with less slope than its speed suggests; this slack is why Chapter 3 gets an inequality in general and needs extra structure for equality.

Check your understanding

Fix $u$ . How does $\varphi_\tau(u)$ depend on $\tau$ ?

It is nonincreasing in $\tau$ , and tends to $\varphi(u)$ as $\tau\downarrow0$ (for l.s.c. $\varphi$ ).
It is nondecreasing in $\tau$ .Larger $\tau$ makes the penalty $d^2/2\tau$ smaller for every $v$ , so the infimum can only go down.
It can go either way, depending on $\varphi$ .The monotonicity holds for every $\varphi$ : compare the two infima competitor by competitor.

For each fixed

v

,

\varphi(v)+d^2(u,v)/2\tau

decreases in

\tau

; an infimum of decreasing functions decreases. The derivative formula says more: the rate is exactly

d^2(u,u_\tau)/2\tau^2

, the squared discrete speed over 2.

A step from $u$ with $\tau=0.1$ lands at $u_\tau$ with $d(u,u_\tau)=0.3$ . What can you conclude in a general metric space?

$|\partial\varphi|(u_\tau)\le3$
$|\partial\varphi|(u)\le3$ The estimate is at the endpoint $u_\tau$ . At the start $u$ the slope can be anything; for the jump function in the explorer it can even be $0$ at both ends.
$|\partial\varphi|(u_\tau)=3$ Equality holds for $C^1$ energies in $\R^d$ , where $(u-u_\tau)/\tau=\nabla\varphi(u_\tau)$ . In general only the inequality survives: see the worked example with $|x|\le\tau$ .

If

w

is near

u_\tau

, minimality gives

\varphi(u_\tau)-\varphi(w)\le\big(d^2(u,w)-d^2(u,u_\tau)\big)/2\tau\le d(u_\tau,w)\,\big(d(u,w)+d(u,u_\tau)\big)/2\tau

. Divide by

d(u_\tau,w)

and let

w\to u_\tau

.

$\varphi$ is the jump function: $0$ for $x\le0$ and $1$ for $x>0$ . What is $\varphi_\tau(x)$ for $x>0$ ?

$\min\big(1,\ x^2/2\tau\big)$
$1$ You can also jump to $v=0$ , where $\varphi=0$ , at cost $x^2/2\tau$ .
$x^2/2\tau$ For large $x$ it is cheaper to stay put and pay $\varphi(x)=1$ .

The only competitors worth considering are

v=x

(value 1) and

v=0

(value

x^2/2\tau

). The envelope is continuous even though

\varphi

is not; at

x=\sqrt{2\tau}

the minimizer jumps from 0 to

x

and

J_\tau[x]

has two points. Lower semicontinuity of

\varphi

(

\varphi(0)=0

, not 1) is what makes

v=0

a minimizer at all.

Practice

The envelope of a quadraticEverything explicit

For $\varphi(x)=\tfrac a2x^2$ on $\R$ with $a>0$ , compute $x_\tau$ and $\varphi_\tau$ . Verify the derivative formula.

Solution

$av+(v-x)/\tau=0$ gives $x_\tau=x/(1+a\tau)$ . Then

\varphi_\tau(x)=\frac a2\frac{x^2}{(1+a\tau)^2}+\frac{1}{2\tau}\Big(\frac{a\tau x}{1+a\tau}\Big)^2=\frac a2\,\frac{x^2}{1+a\tau}.

So

\frac{d}{d\tau}\varphi_\tau=-\frac{a^2x^2}{2(1+a\tau)^2}

, and

\frac{|x-x_\tau|^2}{2\tau^2}=\frac{(a\tau x)^2}{2\tau^2(1+a\tau)^2}

is the same. The envelope is again quadratic, with the smaller coefficient

a/(1+a\tau)<1/\tau

.

The discrete energy inequality with slopesDe Giorgi's interpolation

Assuming the derivative formula and $\varphi_r(u)\to\varphi(u)$ as $r\downarrow0$ , prove

\varphi(u)-\varphi(u_\tau)\ge\frac{d^2(u,u_\tau)}{2\tau}+\frac12\int_0^\tau|\partial\varphi|^2(u_r)\,dr

for any choice

u_r\in J_r[u]

.

Hint

$\varphi_\tau(u)=\varphi(u_\tau)+d^2(u,u_\tau)/2\tau$ . Write $\varphi(u)-\varphi_\tau(u)$ as an integral in $r$ .

Solution

$\varphi(u)-\varphi_\tau(u)=\int_0^\tau\frac{d^2(u,u_r)}{2r^2}dr$ by the derivative formula ( $r\mapsto\varphi_r(u)$ is monotone and locally Lipschitz on $(0,\infty)$ ). The slope estimate gives $\frac{d^2(u,u_r)}{r^2}\ge|\partial\varphi|^2(u_r)$ . Substitute $\varphi_\tau(u)=\varphi(u_\tau)+d^2(u,u_\tau)/2\tau$ and rearrange.

SimulationAmbrosio–Gigli–Savaré, Ch. 4: Uniqueness, Generation of Contraction Semigroups, Error Estimates

λ-convexity and contraction

Without convexity, gradient flows can split (Module 1, quiz 3). With $\lambda$ -convexity they cannot: two flows drift apart at most like $e^{-\lambda t}$ , so the flow is unique and stable, and the minimizing-movement scheme converges with an explicit rate.

The idea

$\lambda$ -convexity.

\varphi

is

\lambda

-convex along a constant-speed geodesic

\gamma

from

v_0

to

v_1

if

\varphi(\gamma_t)\le(1-t)\varphi(v_0)+t\varphi(v_1)-\frac\lambda2t(1-t)\,d^2(v_0,v_1).

In

\R^d

, for

C^2

functions this means

\nabla^2\varphi\ge\lambda I

.

\lambda

may be negative:

\tfrac14(x^2-1)^2

is

(-1)

-convex.

Assumption of Ch. 4. Any two points are joined by some curve along which

v\mapsto\Phi(\tau,w;v)

is

(1/\tau+\lambda)

-convex, for every base point

w

and

0<\tau<1/\lambda^-

. It holds for

\lambda

-convex

\varphi

on Hilbert spaces and on nonpositively curved spaces. In the Wasserstein space it holds along generalized geodesics (Module 9).

Evolution variational inequality (EVI). Under that assumption, with

S

complete and

\varphi

proper, lower semicontinuous and coercive (bounded below as in Ch. 2), for every

u_0

in the closure of the domain the scheme converges to a unique curve

u

, and

u

is characterised by

\frac12\frac{d}{dt}d^2(u(t),v)+\frac\lambda2d^2(u(t),v)\le\varphi(v)-\varphi(u(t))\qquad\text{for all }v.

Contraction and error. Two solutions satisfy

d(u(t),w(t))\le e^{-\lambda t}d(u_0,w_0)

. For

\lambda\ge0

and constant step

\tau

, the discrete solution obeys

d(U^N,u(N\tau))\le\tau|\partial\varphi|(u_0)/\sqrt2

, and

d^2\le\tau\,(\varphi(u_0)-\inf\varphi)

if only

\varphi(u_0)<\infty

.

In $\R^d$ the EVI is the first-order form of $\lambda$ -convexity, $\varphi(v)\ge\varphi(u)+\langle\nabla\varphi(u),v-u\rangle+\tfrac\lambda2|v-u|^2$ , with $-\nabla\varphi(u)=u'$ substituted. Its advantage is that it involves only distances and energies, and it still makes sense when $\varphi$ has corners.

Explore

Energy φ on ℝ²

flow from p flow from q · drag the start points, then run

d(u(t),w(t))

bound

e^{-\lambda t}d(u_0,w_0)

Worked example

Prove the contraction estimate for a $C^2$ function $\varphi$ on $\R^d$ with $\nabla^2\varphi\ge\lambda I$ , and show it cannot be improved.

What inequality does $\nabla^2\varphi\ge\lambda I$ give for $\nabla\varphi(x)-\nabla\varphi(y)$ ?

Integrate the Hessian along the segment: $\nabla\varphi(x)-\nabla\varphi(y)=\int_0^1\nabla^2\varphi(y+s(x-y))\,(x-y)\,ds$ , so
$\langle\nabla\varphi(x)-\nabla\varphi(y),\,x-y\rangle\ge\lambda|x-y|^2.$
Let $u,w$ be two gradient flows. Differentiate $\tfrac12|u-w|^2$ .

$\frac{d}{dt}\frac12|u-w|^2=\langle u'-w',u-w\rangle=-\langle\nabla\varphi(u)-\nabla\varphi(w),u-w\rangle\le-\lambda|u-w|^2.$
Conclude.

With $D=|u-w|^2$ , $D'\le-2\lambda D$ , so $(e^{2\lambda t}D)'\le0$ and $|u(t)-w(t)|\le e^{-\lambda t}|u_0-w_0|$ . For $\lambda>0$ the flows merge; for $\lambda=0$ they never separate; for $\lambda<0$ they may separate, but at a controlled rate, which is still enough for uniqueness.
Show the bound is sharp.

For $\varphi(x)=\tfrac\lambda2|x|^2$ the flow is $u(t)=e^{-\lambda t}u_0$ , so $|u(t)-w(t)|=e^{-\lambda t}|u_0-w_0|$ exactly. In the explorer, the saddle with both points on a vertical line shows equality with $\lambda=-1$ .

Check your understanding

What is the largest $\lambda$ for which $\varphi(x,y)=x^2+y^4$ is $\lambda$ -convex on $\R^2$ ?

$\lambda=2$ That is the $x$ -direction. In the $y$ -direction the second derivative $12y^2$ vanishes at $y=0$ .
$\lambda=0$
None: $\varphi$ is not convex.Both terms are convex functions, so $\varphi$ is convex.

\nabla^2\varphi=\operatorname{diag}(2,12y^2)

, whose smallest eigenvalue has infimum 0. So flows contract (weakly) but nothing forces exponential convergence in

y

: indeed

y'=-4y^3

decays only like

t^{-1/2}

.

$\varphi$ is convex ( $\lambda=0$ ) but has corners, like $|x|+\tfrac12y^2$ . Two flows start at distance 1. After time 5 their distance is

at most 1.
exactly 1.Contraction is an upper bound. In the corner example, two points on the same side of the corner come together as they stick to it.
possibly more than 1, because of the corners.The EVI needs no smoothness: convexity alone gives contraction. Try the corner in the explorer.

The EVI holds for every convex

\varphi

(for

|x|

the flow is soft thresholding, which is 1-Lipschitz), and EVI implies contraction. Corners can only make trajectories merge, never cross.

For the saddle $\tfrac12(x^2-y^2)$ ( $\lambda=-1$ ), what does the theory give?

$d(u(t),w(t))\le e^{t}d(u_0,w_0)$ : flows separate at most exponentially, so they are still unique.
Nothing: uniqueness needs $\lambda\ge0$ .Any real $\lambda$ gives uniqueness. Non-uniqueness needs a failure of semiconvexity, like $-|x|$ at the origin.
The distance still decreases.Two points separated vertically move apart like $e^{t}$ .

If

u_0=w_0

the bound gives

d(u(t),w(t))\le e^{t}\cdot0=0

. Semiconvexity,

\lambda\in\R

, is all that uniqueness needs. Compare

-|x|

, whose slope jumps at the top and which is not

\lambda

-convex for any

\lambda

.

Practice

Exponential decay of the energyλ > 0 and the Łojasiewicz inequality

Let $\varphi\in C^1(\R^d)$ be $\lambda$ -convex with $\lambda>0$ and minimizer $\bar u$ . Show $\varphi(u)-\varphi(\bar u)\le|\nabla\varphi(u)|^2/2\lambda$ , and deduce $\varphi(u(t))-\varphi(\bar u)\le e^{-2\lambda t}\big(\varphi(u_0)-\varphi(\bar u)\big)$ .

Hint

Minimize the right side of $\varphi(v)\ge\varphi(u)+\langle\nabla\varphi(u),v-u\rangle+\tfrac\lambda2|v-u|^2$ over $v$ .

Solution

The minimum over $v$ of the right side is $\varphi(u)-|\nabla\varphi(u)|^2/2\lambda$ , and the left side is at least $\varphi(\bar u)$ . Along the flow, $\frac{d}{dt}(\varphi(u)-\varphi(\bar u))=-|\nabla\varphi(u)|^2\le-2\lambda(\varphi(u)-\varphi(\bar u))$ , and Gronwall finishes.

Step size and convexityWhen is one step convex?

For the double well $\varphi(x)=\tfrac14(x^2-1)^2$ , find the best $\lambda$ , and the range of $\tau$ for which $\Phi(\tau,a;\cdot)$ is strictly convex for every $a$ . Relate this to quiz 3 of Module 2.

Solution

$\varphi''(x)=3x^2-1\ge-1$ , so $\lambda=-1$ . $\Phi''=3v^2-1+1/\tau\ge1/\tau-1$ . For $\tau<1=1/(-\lambda)$ this is bounded below by a positive constant; at $\tau=1$ , $\Phi''=3v^2$ vanishes only at $v=0$ , so $\Phi$ is still strictly convex; for $\tau>1$ , $\Phi''(0)<0$ . So the range is $\tau\le1$ , and for such $\tau$ every step has exactly one minimizer, so the scheme is well defined. At $\tau=2$ , outside this range, the step from $0$ had two minimizers.

InteractiveAmbrosio–Gigli–Savaré, Ch. 5: Preliminary Results on Measure Theory

Push-forwards and narrow convergence

Part II moves from points to probability measures. Two tools carry most of the weight: pushing a measure forward through a map (how mass is moved), and narrow convergence (how measures are compared in the limit).

The idea

Push-forward. For a Borel map

T:X\to Y

and

\mu\in\mathscr P(X)

,

T_\#\mu(B)=\mu(T^{-1}(B))

. Equivalently

\displaystyle\int f\,d(T_\#\mu)=\int f\circ T\,d\mu

for bounded Borel

f

.

Change of variables. If

\mu=\rho\,\mathcal L^d

and

T

is injective and differentiable (approximate differentiability suffices, Ch. 5.5) with

\det\nabla T>0

, then

T_\#\mu=\frac{\rho}{\det\nabla T}\circ T^{-1}\;\mathcal L^d\quad\text{on }T(X).

In one dimension:

T_\#\mu

has density

\sum_{x:\,T(x)=y}\rho(x)/|T'(x)|

, and a flat piece of

T

creates an atom.

Narrow convergence.

\mu_n\to\mu

narrowly if

\int f\,d\mu_n\to\int f\,d\mu

for every bounded continuous

f

. Prokhorov: on a complete separable metric space, a family is relatively compact for narrow convergence iff it is tight: for each

\varepsilon

there is a compact

K

with

\mu(X\smallsetminus K)<\varepsilon

for all members.

Uniformly integrable moments.

\lim_{R\to\infty}\sup_n\int_{|x|>R}|x|^p\,d\mu_n=0

. Narrow convergence plus this is exactly convergence in the Wasserstein distance

W_p

(Ch. 7). Without it, a vanishing amount of mass can run off far enough to keep the distance large.

Chapter 5 also covers disintegration (writing a plan on $X\times Y$ as a family of conditional measures $\gamma_x$ ) and when plans converging narrowly implies maps converging; those reappear in the next two modules.

Explore

Start from a map

source

\mu

(along

x

) map

T

· drag the knots up and down

density of

T_\#\mu

atoms (mass written above)

Worked example

Let $\mu_n=(1-\tfrac1n)\delta_0+\tfrac1n\delta_{x_n}$ on $\R$ with $x_n\to\infty$ . Decide when $\mu_n\to\delta_0$ , and in what sense.

Show $\mu_n\to\delta_0$ narrowly, whatever $x_n$ is.

For bounded continuous $f$ , $\int f\,d\mu_n=(1-\tfrac1n)f(0)+\tfrac1nf(x_n)$ , and $|f(x_n)|/n\le\|f\|_\infty/n\to0$ . So the integrals converge to $f(0)$ .
Take $x_n=n$ . Compute $\int|x|\,d\mu_n$ and $\int|x|^2\,d\mu_n$ .

$\int|x|\,d\mu_n=1$ and $\int|x|^2\,d\mu_n=n$ , while $\delta_0$ has both equal to 0. The moments do not converge: the escaping mass $1/n$ carries a fixed amount of first moment to infinity, so the moments are not uniformly integrable.
The only plan from $\mu_n$ to $\delta_0$ sends everything to 0. Compute $W_1(\mu_n,\delta_0)$ and $W_2(\mu_n,\delta_0)$ for $x_n=n$ .

$W_1=\tfrac1n\cdot n=1$ and $W_2=\big(\tfrac1n\cdot n^2\big)^{1/2}=\sqrt n$ . Neither tends to 0, even though the narrow limit is $\delta_0$ .
For which powers $x_n=n^a$ does $W_2(\mu_n,\delta_0)\to0$ ?

$W_2^2=n^{2a-1}\to0$ iff $a<\tfrac12$ . At $a=\tfrac12$ it stays equal to 1: narrow convergence holds, $W_2$ convergence fails, and the second moments are bounded but not uniformly integrable.

Check your understanding

Does $\delta_{1/n}$ converge narrowly to $\delta_0$ ?

Yes.
No: $\delta_{1/n}(\{0\})=0$ for every $n$ , but $\delta_0(\{0\})=1$ .Narrow convergence asks about integrals of continuous functions, not about the mass of every set. Mass may pile up on the boundary of a set in the limit.

f(1/n)\to f(0)

for every continuous

f

. The general rule (Portmanteau):

\limsup\mu_n(C)\le\mu(C)

for closed

C

and

\liminf\mu_n(U)\ge\mu(U)

for open

U

. Here

\{0\}

is closed and

0\le1

.

$\mu$ is uniform on $[-1,1]$ and $T(x)=x^2$ . What is the density of $T_\#\mu$ on $(0,1]$ ?

$\dfrac{1}{2\sqrt y}$
$\dfrac{1}{4\sqrt y}$ Each $y$ has two preimages, $\pm\sqrt y$ , and both contribute.
$1$ (uniform) $T$ compresses intervals near $0$ (its derivative vanishes there), so mass piles up near $y=0$ .

Each preimage contributes

\rho(x)/|T'(x)|=\tfrac12/(2\sqrt y)

, and there are two. Check:

\int_0^1\frac{dy}{2\sqrt y}=1

. The "Fold" preset in the explorer shows the same sum over preimages.

Which sequence in $\mathscr P(\R)$ has no narrowly convergent subsequence?

$\delta_{(-1)^n}$ It is tight (all mass in $[-1,1]$ ); the even and odd subsequences converge.
$\tfrac12\delta_0+\tfrac12\delta_n$
the Gaussians $N(0,1/n)$ They converge to $\delta_0$ .

Half the mass escapes to infinity, so the family is not tight. A narrow limit would have to give mass

\tfrac12

to

\{0\}

and nothing elsewhere, which is not a probability measure. Prokhorov's theorem says tightness is exactly what is missing.

Practice

Affine images of GaussiansPush-forward in practice

Show that if $\mu=N(m,\sigma^2)$ on $\R$ and $T(x)=ax+b$ with $a\neq0$ , then $T_\#\mu=N(am+b,a^2\sigma^2)$ .

Solution

By change of variables, $T_\#\mu$ has density $\rho\big((y-b)/a\big)/|a|=\frac{1}{\sqrt{2\pi}|a|\sigma}\exp\!\big(-\frac{(y-b-am)^2}{2a^2\sigma^2}\big)$ . Every pair of Gaussians on $\R$ is linked by such a map with $a=\sigma_1/\sigma_0>0$ ; in Module 7 you will see it is the optimal one.

Moments are lower semicontinuousTruncation

Show that if $\mu_n\to\mu$ narrowly, then $\int|x|^2\,d\mu\le\liminf_n\int|x|^2\,d\mu_n$ . Give an example with strict inequality.

Hint

$\min(|x|^2,R)$ is bounded and continuous.

Solution

$\int\min(|x|^2,R)\,d\mu=\lim_n\int\min(|x|^2,R)\,d\mu_n\le\liminf_n\int|x|^2\,d\mu_n$ . Let $R\to\infty$ and use monotone convergence. The worked example with $x_n=\sqrt n$ gives $0<1$ .

InteractiveAmbrosio–Gigli–Savaré, Ch. 6: The Optimal Transportation Problem

Optimal transport

Moving one distribution of mass onto another costs something; the cheapest way to do it is the optimal transport problem. Optimal plans are recognised by a simple local test: no small rearrangement of who goes where can save anything.

The idea

Monge and Kantorovich. Monge: minimize

\int c(x,T(x))\,d\mu

over maps with

T_\#\mu=\nu

. Such maps may not exist (

\mu=\delta_0

,

\nu=\tfrac12\delta_{-1}+\tfrac12\delta_1

). Kantorovich relaxes to plans:

\min\Big\{\int c\,d\gamma:\ \gamma\in\Gamma(\mu,\nu)\Big\},\qquad\Gamma(\mu,\nu)=\{\gamma\in\mathscr P(X\times Y):\ \pi^1_\#\gamma=\mu,\ \pi^2_\#\gamma=\nu\}.

A minimizer exists for lower semicontinuous costs bounded below:

\Gamma(\mu,\nu)

is narrowly compact.

Cyclical monotonicity. A set

\Gamma\subset X\times Y

is

c

-cyclically monotone if for all

(x_1,y_1),\dots,(x_n,y_n)\in\Gamma

and permutations

\sigma

,

\sum c(x_i,y_i)\le\sum c(x_i,y_{\sigma(i)})

.

Optimality (Ch. 6.1). For a continuous cost with finite optimal cost (and a mild integrability bound on

c

), a plan is optimal iff its support is

c

-cyclically monotone; equivalently, iff Kantorovich's dual problem has a matching pair of potentials.

Brenier (the case $c=|x-y|^2$ ). If

\mu

is absolutely continuous on

\R^d

(and both measures have finite second moments), the optimal plan is unique and induced by a map

T=\nabla\psi

with

\psi

convex. Chapter 6 extends this to "regular"

\mu

and to Hilbert spaces.

For quadratic cost, the two-point test reads $\langle x_1-x_2,\,y_1-y_2\rangle\ge0$ : the plan is monotone. For $c=|x-y|$ , optimality forces the segments of a matching not to cross (except in degenerate collinear configurations). For quadratic cost they can cross, but the moving particles never collide.

Explore

sources

x_i

targets

y_j

pairs that a swap would improve · drag points; click a source, then a target, to re-pair

Cost

Matching shown

Move the particles, t 0.00

Worked example

Let $\mu$ be uniform on $[0,1]$ and $\nu$ uniform on $[1,2]$ . Two maps push $\mu$ to $\nu$ : the translation $T(x)=x+1$ and the flip $S(x)=2-x$ . Which is optimal, for $c=|x-y|$ and for $c=|x-y|^2$ ?

Compute both costs for $c=|x-y|$ .

Translation: $\int_0^1 1\,dx=1$ . Flip: $\int_0^1|2-2x|\,dx=1$ . Equal.
Show that no plan does better than 1 for $c=|x-y|$ .

For any $\gamma\in\Gamma(\mu,\nu)$ , $\int|x-y|\,d\gamma\ge\int(y-x)\,d\gamma=\int y\,d\nu-\int x\,d\mu=\tfrac32-\tfrac12=1$ . So both maps are optimal: with linear cost the optimal plan need not be unique.
Now $c=|x-y|^2$ . Compute both costs.

Translation: 1. Flip: $\int_0^1(2-2x)^2\,dx=\tfrac43$ . The translation is cheaper.
Show the translation is the unique optimal plan for $c=|x-y|^2$ .

By Jensen, $\int(y-x)^2\,d\gamma\ge\big(\int(y-x)\,d\gamma\big)^2=1$ , with equality iff $y-x$ is $\gamma$ -a.e. constant, i.e. $\gamma$ is concentrated on $y=x+1$ . That plan is the translation. Strict convexity of the cost is what buys uniqueness, and the optimal map is monotone, as the two-point test predicts.

Check your understanding

$\mu$ and $\nu$ are each uniform on $n$ points. Must an optimal Kantorovich plan split mass?

No: some optimal plan is a permutation (a perfect matching).
Yes, in general.The plans form a polytope of doubly stochastic matrices (divided by $n$ ); a linear cost attains its minimum at a vertex, and the vertices are permutations.
Only for quadratic cost is there an optimal permutation.The vertex argument works for any cost.

That is the Birkhoff–von Neumann theorem. It is why the explorer only searches over the

5!=120

matchings. With unequal numbers of points or unequal weights, splitting can be forced (see practice problem 2).

For $c=|x-y|^2$ on $\R^d$ , when is pairing $x_1\to y_1,\ x_2\to y_2$ no worse than swapping the targets?

When $\langle x_1-x_2,\ y_1-y_2\rangle\ge0$ .
When the segments $[x_1,y_1]$ and $[x_2,y_2]$ do not cross.Not crossing is what optimality forces for $c=|x-y|$ . Press "Crossing example": for squared cost the crossing pairing is the optimal one.
When $|x_1-x_2|\le|y_1-y_2|$ .Expand both costs: the squared norms cancel and only inner products remain.

|x_1-y_1|^2+|x_2-y_2|^2-|x_1-y_2|^2-|x_2-y_1|^2=-2\langle x_1-x_2,y_1-y_2\rangle

. Monotonicity of the support is the discrete shadow of Brenier's theorem: the gradient of a convex function is a monotone map.

$\mu$ is uniform on the unit disc and $\nu$ uniform on the disc of radius 2, both centred at 0. Which map is optimal for $c=|x-y|^2$ ?

$T(x)=2x$
$T(x)=2Rx$ , $R$ a rotation by $90^\circ$ It also pushes $\mu$ to $\nu$ , but it is not the gradient of a convex function. Its cost is $\int|2Rx-x|^2d\mu=5\int|x|^2d\mu$ , versus $\int|x|^2d\mu$ for $2x$ .
There are many optimal maps. $\mu$ is absolutely continuous, so Brenier's theorem gives uniqueness.

2x=\nabla(|x|^2)

and

|x|^2

is convex, so by Brenier it is the optimal map. Its cost is

\int|x|^2\,d\mu=\tfrac12

.

Practice

Monotone means optimal on the lineThe two-point test in 1-D

On $\R$ with $c=|x-y|^2$ , show that a plan whose support satisfies the two-point test is monotone: if $(x_1,y_1),(x_2,y_2)$ are in the support and $x_1<x_2$ , then $y_1\le y_2$ . Why does this single out one plan?

Solution

The test says $(x_1-x_2)(y_1-y_2)\ge0$ , so $x_1<x_2$ forces $y_1\le y_2$ . A monotone plan sends the $u$ -th quantile of $\mu$ to the $u$ -th quantile of $\nu$ , for every $u\in(0,1)$ , which determines it: $\gamma=(F_\mu^{-1},F_\nu^{-1})_\#\mathcal L^1|_{(0,1)}$ . That is the formula behind the next module.

When mass must splitThree atoms to two

Let $\mu=\tfrac13(\delta_0+\delta_1+\delta_2)$ and $\nu=\tfrac12(\delta_{1/2}+\delta_{3/2})$ . Find the optimal plan for $c=|x-y|^2$ and its cost.

Hint

By the previous problem the plan is monotone: fill the targets from left to right.

Solution

$0\to\tfrac12$ with mass $\tfrac13$ ; the atom at 1 splits, $\tfrac16$ to $\tfrac12$ and $\tfrac16$ to $\tfrac32$ ; $2\to\tfrac32$ with mass $\tfrac13$ . Every move has length $\tfrac12$ , so the cost is $\tfrac14$ and $W_2(\mu,\nu)=\tfrac12$ . No map can do this: $T_\#\mu$ for a map gives each target a multiple of $\tfrac13$ .

Edit it yourselfAmbrosio–Gigli–Savaré, Ch. 7: The Wasserstein Distance and its Behaviour along Geodesics

The Wasserstein distance

The optimal cost turns the probability measures into a metric space, the space where Part II's gradient flows live. On the line everything is explicit: sort the mass, and compare quantiles.

The idea

Wasserstein distance. On

\mathscr P_p(X)=\{\mu:\int|x|^p\,d\mu<\infty\}

,

W_p(\mu,\nu)=\Big(\min_{\gamma\in\Gamma(\mu,\nu)}\int|x-y|^p\,d\gamma\Big)^{1/p}.

It is a complete separable metric, and

W_p(\mu_n,\mu)\to0

iff

\mu_n\to\mu

narrowly with uniformly integrable

p

-moments.

On the line. With

F^{-1}

the quantile function, the monotone plan is optimal (Module 6) and

W_p^p(\mu,\nu)=\int_0^1\big|F_\mu^{-1}(u)-F_\nu^{-1}(u)\big|^p\,du,\qquad W_1(\mu,\nu)=\int_\R|F_\mu-F_\nu|\,dx.

Geodesics. If

\gamma

is optimal for

W_2(\mu_0,\mu_1)

, then

\mu_t=\big((1-t)\pi^1+t\pi^2\big)_\#\gamma

is a constant-speed geodesic:

W_2(\mu_s,\mu_t)=|t-s|\,W_2(\mu_0,\mu_1)

. This is displacement interpolation: every bit of mass travels along a straight line. On the line,

F_{\mu_t}^{-1}=(1-t)F_{\mu_0}^{-1}+tF_{\mu_1}^{-1}

.

Mixtures are not geodesics. The linear interpolation

(1-t)\mu_0+t\mu_1

fades one measure out while the other fades in.

W_2\big((1-t)\delta_0+t\delta_1,\ \delta_0\big)=\sqrt t

, so this curve is not even Lipschitz in

W_2

.

Curvature (Ch. 7.3).

\mathscr P_2(X)

is positively curved: along a geodesic,

W_2^2(\mu_t,\nu)\ge(1-t)W_2^2(\mu_0,\nu)+tW_2^2(\mu_1,\nu)-t(1-t)W_2^2(\mu_0,\mu_1)

. On

\R

the quantile map is an isometry into

L^2(0,1)

, so

\mathscr P_2(\R)

is flat and equality holds.

Explore

Edit

Interpolation

t 0.50

\mu_0

\mu_1

\mu_t

· click or drag on the bars to edit

Quantile functions

F^{-1}(u)

.

W_2^2

is the mean squared vertical gap,

W_1

the shaded area.

Worked example

Let $\mu_0$ be uniform on $[0,1]$ and $\mu_1$ uniform on $[2,4]$ . Compute $W_2(\mu_0,\mu_1)$ , the geodesic midpoint, and compare with the mixture midpoint $\nu=\tfrac12\mu_0+\tfrac12\mu_1$ .

Write down the quantile functions and $W_2(\mu_0,\mu_1)$ .

$F_0^{-1}(u)=u$ , $F_1^{-1}(u)=2+2u$ . So $W_2^2=\int_0^1(2+u)^2\,du=4+2+\tfrac13=\tfrac{19}3$ , and $W_2\approx2.517$ .
Find the displacement midpoint $\mu_{1/2}$ and check $W_2(\mu_0,\mu_{1/2})=\tfrac12W_2(\mu_0,\mu_1)$ .

$F_{1/2}^{-1}=\tfrac12u+\tfrac12(2+2u)=1+\tfrac32u$ : uniform on $[1,2.5]$ . Then $W_2^2(\mu_0,\mu_{1/2})=\int_0^1(1+\tfrac u2)^2du=\tfrac{19}{12}=\tfrac14\cdot\tfrac{19}3$ . The midpoint is a single interval of intermediate length, not two bumps.
Find the quantile function of the mixture $\nu$ .

$\nu$ has mass $\tfrac12$ spread on $[0,1]$ and $\tfrac12$ on $[2,4]$ . So $F_\nu^{-1}(u)=2u$ for $u<\tfrac12$ and $4u$ for $u>\tfrac12$ .
Is $\nu$ on a geodesic between $\mu_0$ and $\mu_1$ ?

$W_2^2(\mu_0,\nu)=\int_0^{1/2}u^2\,du+\int_{1/2}^1 9u^2\,du=\tfrac1{24}+\tfrac{63}{24}=\tfrac83$ , and $W_2^2(\nu,\mu_1)=\int_0^{1/2}4\,du+\int_{1/2}^1(2u-2)^2du=2+\tfrac16=\tfrac{13}6$ . Then $W_2(\mu_0,\nu)+W_2(\nu,\mu_1)\approx1.633+1.472=3.105>2.517$ . The triangle inequality is strict, so $\nu$ lies on no geodesic between them. Load the "Split" preset and compare the two modes.

Check your understanding

$\mu=\tfrac12\delta_0+\tfrac12\delta_2$ and $\nu=\delta_1$ . What is $W_2(\mu,\nu)$ ?

$0$ , since they have the same mean. $W_2=0$ only for equal measures. Matching the mean is not enough.
$1$
$\sqrt2$ There is only one plan, and every unit of mass moves distance 1.

The only plan to a Dirac sends everything to it:

W_2^2=\tfrac12\cdot1+\tfrac12\cdot1=1

. In general

W_2^2(\mu,\delta_y)=\int|x-y|^2d\mu

, which is the variance when

y

is the mean.

Along the mixture $\mu_t=(1-t)\delta_0+t\delta_1$ , what is $W_2(\mu_0,\mu_t)$ ?

$\sqrt t$
$t$ That is $W_2$ along the displacement geodesic $\delta_t$ , where all the mass moves a distance $t$ . Here mass $t$ moves distance 1.
$t^2$ The squared cost is $t\cdot 1^2=t$ , and $W_2$ is its square root, not its square.

The cost is

t\cdot1^2

, so

W_2=\sqrt t

. The average speed

\sqrt t/t

blows up as

t\to0

. In fact

W_2(\mu_s,\mu_t)=\sqrt{|t-s|}

for all

s,t

, so the metric derivative is infinite everywhere and the mixture has infinite

W_2

-length on every time interval, while

W_1=t

is perfectly linear. Linear in the "vertical" sense (mass) and linear in the "horizontal" sense (position) are different notions.

$\nu$ is $\mu$ translated by a vector $h\in\R^d$ . What is $W_2(\mu,\nu)$ ?

$|h|$ , for every $\mu$
at most $|h|$ , and smaller when $\mu$ is spread outSome other plan might move mass less far on average? Jensen says no: $\int|x-y|^2d\gamma\ge|\int(x-y)\,d\gamma|^2=|h|^2$ .
it depends on the shape of $\mu$ The lower bound from the means is attained by the translation itself, whatever $\mu$ is.

The translation achieves

|h|^2

and Jensen shows nothing beats it. In general

W_2^2(\mu,\nu)\ge|m_\mu-m_\nu|^2

, with equality iff

\nu

is a translate of

\mu

.

Practice

Gaussians on the lineA closed form

Show $W_2^2\big(N(m_0,\sigma_0^2),N(m_1,\sigma_1^2)\big)=(m_0-m_1)^2+(\sigma_0-\sigma_1)^2$ on $\R$ , and describe the geodesic.

Solution

Quantiles are $m_i+\sigma_iz(u)$ with $z=\Phi^{-1}$ , and $\int_0^1z\,du=0$ , $\int_0^1z^2du=1$ . So $W_2^2=\int\big((m_0-m_1)+(\sigma_0-\sigma_1)z\big)^2du=(m_0-m_1)^2+(\sigma_0-\sigma_1)^2$ . The geodesic is $N(m_t,\sigma_t^2)$ with $m_t$ and $\sigma_t$ (the standard deviation, not the variance) affine in $t$ .

W_1

as an areaCDFs versus quantiles

Explain why $\int_0^1|F_\mu^{-1}-F_\nu^{-1}|\,du=\int_\R|F_\mu-F_\nu|\,dx$ .

Solution

Both are the area of the region between the graphs of $F_\mu$ and $F_\nu$ in the $(x,u)$ plane: integrating horizontally slice by slice (fixed $u$ ) gives the left side, vertically (fixed $x$ ) the right side. The graph of $F^{-1}$ is the graph of $F$ reflected in the diagonal, with vertical jumps filled in. For $p>1$ there is no such formula in terms of $F$ alone.

Animated lessonAmbrosio–Gigli–Savaré, Ch. 8: A.C. Curves in

\mathscr P_p(X)

and the Continuity Equation

The continuity equation

A curve of probability measures moves because its mass moves, with some velocity field. Many velocity fields can produce the same curve; the cheapest one is a gradient, and its kinetic energy is the curve's speed in $W_2$ . That makes the Wasserstein space look like a Riemannian manifold.

The idea

Continuity equation.

\partial_t\mu_t+\nabla\cdot(v_t\mu_t)=0

in the sense of distributions:

\frac{d}{dt}\int\phi\,d\mu_t=\int\langle\nabla\phi,v_t\rangle\,d\mu_t\qquad\text{for all }\phi\in C_c^\infty(\R^d).

If

v

is smooth,

\mu_t=(X_t)_\#\mu_0

where

X_t

is the flow of

v

: mass is carried along the trajectories.

Absolutely continuous curves (Ch. 8.3). A curve

\mu_t

in

\mathscr P_p(\R^d)

is absolutely continuous iff it solves the continuity equation for some

v_t

with

\int\|v_t\|_{L^p(\mu_t)}dt<\infty

. Every such

v

satisfies

\|v_t\|_{L^p(\mu_t)}\ge|\mu'|(t)

, and there is one with equality for a.e.

t

.

Tangent space (Ch. 8.4). For

p=2

, the optimal

v_t

is the unique one in

\operatorname{Tan}_{\mu}\mathscr P_2=\overline{\{\nabla\phi:\phi\in C_c^\infty\}}^{\,L^2(\mu)}.

Two fields give the same curve iff their difference

w

satisfies

\nabla\cdot(w\mu)=0

; removing that part only lowers the kinetic energy.

Benamou–Brenier.

\displaystyle W_2^2(\mu_0,\mu_1)=\min\Big\{\int_0^1\!\!\int|v_t|^2\,d\mu_t\,dt\Big\}

over all solutions of the continuity equation joining

\mu_0

to

\mu_1

. Minimizers move along geodesics with tangent velocity.

Watch

Swirl strength c 2.0

moved by

v=a

moved by

v=a+c\,J(x-m_t)

· rings: density level sets of

\mu_t

A probability measure $\mu_0$ : a Gaussian, drawn as a sample of particles with its density level sets.
Move every particle with the constant field $v=a$ , a gradient (of $\langle a,x\rangle$ ). The measure slides: $\mu_t=N(m_0+ta,\sigma^2I)$ .
Start again with $v=a+c\,J(x-m_t)$ , $J$ the rotation by $90^\circ$ . Particles now swirl around the moving centre.
Yet the rings match: the swirl is divergence-free against the radial density, $\nabla\cdot(J(x-m_t)\rho_t)=0$ . Same curve $\mu_t$ , two velocity fields.
The kinetic energies differ: $|a|^2$ versus $|a|^2+2c^2\sigma^2$ . The curve's speed is $|\mu'|=|a|$ , achieved by the gradient field, which is the tangent vector.

Worked example

On $\R$ , let $\mu_t=N(0,(1+t)^2)$ for $t\in[0,1]$ . Find a velocity field, check the continuity equation, and decide whether the curve is a geodesic.

Write $\mu_t$ as a push-forward of $\mu_0$ and read off a velocity.

$X_t(x)=(1+t)x$ pushes $N(0,1)$ to $N(0,(1+t)^2)$ . A particle at $y=X_t(x)$ moves with speed $\dot X_t(x)=x=y/(1+t)$ , so $v_t(y)=y/(1+t)$ .
Check the weak form of the continuity equation.

With $Z\sim N(0,1)$ , $\frac{d}{dt}\int\phi\,d\mu_t=\frac{d}{dt}\mathbb E\,\phi((1+t)Z)=\mathbb E\big[\phi'((1+t)Z)\,Z\big]=\int\phi'(y)\,\frac{y}{1+t}\,d\mu_t(y)$ .
Compute the kinetic energy $\int|v_t|^2d\mu_t$ . Is $v_t$ tangent?

$\int\frac{y^2}{(1+t)^2}d\mu_t=1$ . And $v_t=\partial_y\big(y^2/2(1+t)\big)$ is a gradient, so it is the tangent field and $|\mu'|(t)=1$ .
Compare the length of the curve with $W_2(\mu_0,\mu_1)$ .

Length $=\int_0^1|\mu'|\,dt=1$ , and $W_2\big(N(0,1),N(0,4)\big)=|1-2|=1$ by the Gaussian formula of Module 7. Length equals distance, so the curve is a geodesic, and the Benamou–Brenier action $\int_0^1\!\int|v_t|^2d\mu_tdt=1=W_2^2$ is minimal.

Check your understanding

On $\R$ , suppose $\mu_t$ has a smooth positive density for every $t$ . How many velocity fields in $L^2(\mu_t)$ solve the continuity equation for this curve?

Exactly one.
Infinitely many, as with the swirl.In one dimension $\partial_x(w\rho)=0$ means $w\rho$ is constant, and integrability forces the constant to be 0.
None, unless the curve is a geodesic.Every absolutely continuous curve has velocity fields; geodesics are the ones whose tangent field has constant norm and is "straight".

There is no room to swirl on the line. Indeed,

v_t(x)=-\partial_tF_t(x)/\rho_t(x)

, where

F_t

is the CDF: the flux through

x

is the rate at which mass to the left of

x

decreases.

$\mu_t=\delta_{x(t)}$ for a smooth path $x(t)$ in $\R^d$ . What is $|\mu'|(t)$ in $W_2$ ?

$|x'(t)|$
$0$ , because a Dirac mass has no density to move. $W_2(\delta_x,\delta_y)=|x-y|$ , so the curve moves exactly as fast as the point.
It is undefined: there is no velocity field on the complement of the support.Only the values of $v_t$ on the support of $\mu_t$ matter, since $\|v_t\|_{L^2(\mu_t)}$ only sees them.

x\mapsto\delta_x

is an isometric embedding of

\R^d

into

\mathscr P_2(\R^d)

. Any field with

v_t(x(t))=x'(t)

works, and

\|v_t\|_{L^2(\mu_t)}=|x'(t)|

.

A curve on $[0,1]$ solves the continuity equation with $\int|v_t|^2d\mu_t=E$ for every $t$ . What follows?

$W_2(\mu_0,\mu_1)\le\sqrt E$
$W_2(\mu_0,\mu_1)=\sqrt E$ Add a swirl: the kinetic energy goes up and the curve stays the same.
$W_2(\mu_0,\mu_1)\ge\sqrt E$ The kinetic energy bounds the speed from above, not below.

W_2(\mu_0,\mu_1)\le\int_0^1|\mu'|\,dt\le\int_0^1\|v_t\|_{L^2(\mu_t)}dt=\sqrt E

. Equality needs both a geodesic and tangent velocities, which is the Benamou–Brenier statement.

Practice

The swirl is invisibleA divergence-free perturbation

Let $\rho(x)=g(|x-m|)$ be a radial density on $\R^2$ and $w(x)=J(x-m)$ . Show $\nabla\cdot(w\rho)=0$ , and compute $\int|w|^2\,d\mu$ for $\mu=N(m,\sigma^2I_2)$ .

Solution

$\nabla\cdot(w\rho)=\rho\,\nabla\cdot w+\langle w,\nabla\rho\rangle$ . The rotation field has zero divergence, and $\nabla\rho$ is parallel to $x-m$ , which is perpendicular to $J(x-m)$ . So both terms vanish. Then $\int|J(x-m)|^2d\mu=\int|x-m|^2d\mu=2\sigma^2$ , the value in the animation's stats.

The velocity on the lineFrom the CDF

On $\R$ , show that $v_t=-\partial_tF_t/\rho_t$ solves the continuity equation for a smooth curve of positive densities $\rho_t$ with CDFs $F_t$ . Check it on the translation $\rho_t(x)=\rho(x-t)$ .

Solution

Integrate $\partial_t\rho_t=-\partial_x(v_t\rho_t)$ from $-\infty$ to $x$ : $\partial_tF_t(x)=-v_t(x)\rho_t(x)$ , assuming the flux vanishes at $-\infty$ . For the translation, $F_t(x)=F(x-t)$ , so $\partial_tF_t=-\rho(x-t)$ and $v_t=1$ .

InteractiveAmbrosio–Gigli–Savaré, Ch. 9: Convex Functionals in

\mathscr P_p(X)

Displacement convexity

Chapter 4 needs $\lambda$ -convexity along geodesics. In the Wasserstein space geodesics move mass rather than mixing it, and a functional can be convex along one kind of interpolation and not the other. Here you test both.

The idea

Geodesic convexity in $\mathscr P_2$ .

\phi

is

\lambda

-convex along geodesics if for every

\mu_0,\mu_1

there is a geodesic

\mu_t

with

\phi(\mu_t)\le(1-t)\phi(\mu_0)+t\phi(\mu_1)-\frac\lambda2t(1-t)W_2^2(\mu_0,\mu_1)

. McCann called this displacement convexity.

The model examples (Ch. 9.3), with $\mu=\rho\,\mathcal L^d$ :

Potential energy $\mathcal V(\mu)=\int V\,d\mu$ is $\lambda$ -convex iff $V$ is $\lambda$ -convex. Along mixtures it is always affine.
Interaction energy $\mathcal W(\mu)=\tfrac12\iint W(x-y)\,d\mu(x)d\mu(y)$ is convex if $W$ is convex. With $W(z)=|z|^2$ on $\R$ it is the variance, which is concave along mixtures.
Internal energy $\mathcal F(\mu)=\int F(\rho)\,dx$ is convex if $F(0)=0$ and $s\mapsto s^dF(s^{-d})$ is convex and nonincreasing on $(0,\infty)$ (McCann's condition). This covers the entropy $F(s)=s\log s$ and $s^m/(m-1)$ for $m\ge1-1/d$ .
Relative entropy with respect to $\gamma=e^{-V}\mathcal L^d$ is $\lambda$ -convex iff $V$ is $\lambda$ -convex (Ch. 9.4): the entropy of a log-concave reference measure.

Generalized geodesics (Ch. 9.2). Because

\mathscr P_2(\R^d)

is positively curved for

d\ge2

,

\tfrac12W_2^2(\cdot,\nu)

is not 1-convex along geodesics, and the assumption of Chapter 4 fails for plain geodesics. The fix is to interpolate between

\mu_0

and

\mu_1

using optimal plans from a third measure (the base point of the step). All the functionals above are convex along these generalized geodesics too, so Chapter 4's theory applies.

Explore

Endpoints

Functional

t 0.50

displacement

\mu_t

mixture

(1-t)\mu_0+t\mu_1

endpoints, and

V

when used

along displacement along mixture · dashed: the chord

Worked example

Compute the entropy $\mathcal H(\mu)=\int\rho\log\rho\,dx$ along the $W_2$ geodesic between two Gaussians on $\R$ , and decide how convex it is.

Compute $\mathcal H\big(N(m,\sigma^2)\big)$ .

$\log\rho=-\tfrac12\log(2\pi\sigma^2)-\frac{(x-m)^2}{2\sigma^2}$ , and the second term averages to $-\tfrac12$ . So $\mathcal H=-\tfrac12\log(2\pi e\sigma^2)=-\log\sigma-\tfrac12\log(2\pi e)$ .
Along the geodesic from $N(m_0,\sigma_0^2)$ to $N(m_1,\sigma_1^2)$ , what is $\mathcal H(\mu_t)$ ?

By Module 7 the geodesic is $N(m_t,\sigma_t^2)$ with $\sigma_t=(1-t)\sigma_0+t\sigma_1$ . So $\mathcal H(\mu_t)=-\log\sigma_t+\text{const}$ .
Is it convex in $t$ ? Is it $\lambda$ -convex for some $\lambda>0$ ?

$\frac{d^2}{dt^2}(-\log\sigma_t)=(\sigma_1-\sigma_0)^2/\sigma_t^2\ge0$ , so it is convex. But if $\sigma_0=\sigma_1$ and $m_0\neq m_1$ (a translation) it is constant along a geodesic of positive length, so no $\lambda>0$ works: the entropy is exactly 0-convex.
Why is the entropy convex along every 1-D geodesic, Gaussian or not?

With quantile $Q$ , $\mathcal H(\mu)=\int_0^1\log\rho(Q(u))\,du=-\int_0^1\log Q'(u)\,du$ (because $\rho(Q)\,Q'=1$ ). Along a geodesic $Q_t'=(1-t)Q_0'+tQ_1'$ is affine in $t$ for each $u$ , and $-\log$ is convex. In the explorer, the entropy curve is convex for every preset.

Check your understanding

For which $V$ is $\mu\mapsto\int V\,d\mu$ convex along every $W_2$ geodesic?

Exactly the convex $V$ .
Every $V$ , since $\mu\mapsto\int V\,d\mu$ is linear.It is linear along mixtures. Along the geodesic $\delta_{x_t}$ between two Dirac masses it equals $V(x_t)$ , which is convex only if $V$ is.
Every $V$ bounded below.Try the double well across the origin in the explorer.

If

V

is

\lambda

-convex,

\int V\,d\mu_t=\int V\big((1-t)x+ty\big)\,d\gamma

inherits

\lambda

-convexity from

V

, with

\int|x-y|^2d\gamma=W_2^2

. Conversely, test on Dirac masses.

Is the entropy $\int\rho\log\rho$ on $\R^d$ $\lambda$ -convex along geodesics for some $\lambda>0$ ?

No: it is constant along translations, which are geodesics.
Yes, with $\lambda=1$ .That is the entropy relative to the standard Gaussian, where the added potential $\int|x|^2/2\,d\mu$ supplies the 1-convexity.
No, it is not even convex.It is convex (0-convex) by McCann's condition: $s^d\cdot s^{-d}\log s^{-d}=-d\log s$ is convex and nonincreasing.

Translating

\mu

by

th

is a geodesic of length

|h|

along which

\int\rho\log\rho

does not change. So the heat flow (Module 11) contracts with

\lambda=0

, not exponentially.

$\operatorname{Var}(\mu)=\tfrac12\iint|x-y|^2d\mu\,d\mu$ . Between $\mu_0=\delta_{-1}$ and $\mu_1=\delta_1$ , along which interpolation is it convex?

Along the displacement interpolation only.
Along both.Along the mixture $(1-t)\delta_{-1}+t\delta_1$ the variance is $4t(1-t)$ .
Along the mixture only.The displacement interpolation is $\delta_{2t-1}$ , with variance 0 throughout: that is convex.

W(z)=|z|^2

is convex, so the interaction energy is displacement convex. Along mixtures,

\operatorname{Var}=\int|x|^2d\mu-|\int x\,d\mu|^2

is affine minus convex: concave. The "Variance" option shows both.

Practice

Entropy relative to a GaussianWhere λ = 1 comes from

Let $\gamma=N(0,I_d)$ . Show $\mathcal H(\mu|\gamma)=\int\rho\log\rho\,dx+\int\tfrac12|x|^2d\mu+\text{const}$ , deduce that it is 1-convex along geodesics, and check the constant 1 is sharp using translations of $\gamma$ .

Solution

The quadratic internal energyQuantiles again

On $\R$ , show $\mu\mapsto\int\rho^2\,dx$ is convex along geodesics.

Hint

$\int\rho^2dx=\int_0^1\rho(Q(u))\,du$ . Express $\rho(Q(u))$ through $Q'$ .

Solution

$\rho(Q(u))=1/Q'(u)$ , so $\int\rho^2dx=\int_0^1\frac{du}{Q'(u)}$ . Along a geodesic $Q_t'$ is affine and positive, and $s\mapsto1/s$ is convex on $(0,\infty)$ . This matches McCann's condition in $d=1$ : $sF(1/s)=1/s$ is convex and nonincreasing.

Draw it yourselfAmbrosio–Gigli–Savaré, Ch. 10: Metric Slope and Subdifferential Calculus in

\mathscr P_p(X)

The Wasserstein gradient

On $\mathscr P_2$ a gradient is a velocity field: the direction in which to move the mass to raise the functional fastest. For the entropy that field is $\nabla\rho/\rho$ , and its kinetic energy is the Fisher information. Draw a density and see its gradient.

The idea

Subdifferential (Ch. 10.1).

\xi\in L^2(\mu;\R^d)

belongs to

\partial\phi(\mu)

if, with

\boldsymbol t_\mu^\nu

the optimal map from

\mu

to

\nu

,

\phi(\nu)-\phi(\mu)\ge\int\big\langle\xi,\ \boldsymbol t_\mu^\nu-\mathrm{id}\big\rangle\,d\mu+o\big(W_2(\mu,\nu)\big).

For

\lambda

-convex

\phi

the

o(\cdot)

can be replaced by

\tfrac\lambda2W_2^2(\mu,\nu)

.

Slope = minimal subgradient. For

\lambda

-convex

\phi

,

|\partial\phi|(\mu)=\min\{\|\xi\|_{L^2(\mu)}:\xi\in\partial\phi(\mu)\}

, and the minimizer

\partial^\circ\phi(\mu)

lies in the tangent space.

For smooth densities the recipe is: take the first variation $\frac{\delta\phi}{\delta\rho}$ (the $L^2$ derivative), then its spatial gradient. Ch. 10.4 makes this rigorous for the model functionals:

potential energy $\int V\,d\mu$ : $\ \xi=\nabla V$ ;
interaction energy $\tfrac12\iint W(x-y)\,d\mu\,d\mu$ ( $W$ even): $\ \xi=(\nabla W)*\mu$ ;
internal energy $\int F(\rho)\,dx$ : $\ \xi=\nabla L_F(\rho)/\rho$ with $L_F(s)=sF'(s)-F(s)$ , which is $\nabla F'(\rho)$ for smooth $\rho$ . For the entropy, $\xi=\nabla\rho/\rho=\nabla\log\rho$ .

Fisher information.

|\partial\mathcal H|^2(\mu)=\int\frac{|\nabla\rho|^2}{\rho}\,dx

, finite only if

\rho\in W^{1,1}_{\mathrm{loc}}

with

\nabla\rho/\rho\in L^2(\mu)

. For the relative entropy with respect to

e^{-V}

,

\xi=\nabla\log(\rho e^{V})

, which vanishes exactly at

\rho\propto e^{-V}

.

The first-variation identity behind all of this: $\frac{d}{d\varepsilon}\phi\big((\mathrm{id}+\varepsilon\eta)_\#\mu\big)\big|_{\varepsilon=0}=\int\langle\xi,\eta\rangle\,d\mu$ . The explorer measures the left side with $\eta=-\xi$ .

Explore

Draw a density with your mouse or finger (it is smoothed and normalised).

\rho

steepest-descent velocity

-\xi

e^{-V}

, when used

Functional

Or start from

Worked example

On $\R$ , take the relative entropy $\phi(\mu)=\int\rho\log\rho\,dx+\int\tfrac12x^2\,d\mu$ and $\mu=N(m,s^2)$ . Compute the Wasserstein gradient, the slope, and the steepest-descent motion.

What is $\xi$ for a general smooth positive $\rho$ ?

The first variation is $\log\rho+1+\tfrac12x^2$ , so $\xi=\rho'/\rho+x$ .
Evaluate it for $\rho=N(m,s^2)$ .

$\rho'/\rho=-(x-m)/s^2$ , so $\xi(x)=\big(1-\tfrac1{s^2}\big)x+\tfrac{m}{s^2}$ : an affine field.
Compute $|\partial\phi|^2(\mu)=\int\xi^2\,d\mu$ .

Write $\xi=ax+b$ with $a=1-1/s^2$ , $b=m/s^2$ . Then $\int\xi^2d\mu=a^2s^2+(am+b)^2$ , and $am+b=m$ . So
$|\partial\phi|^2(\mu)=\Big(s-\frac1s\Big)^2+m^2,$
which vanishes only for $N(0,1)$ , the reference measure.
Move every particle with velocity $-\xi$ . What happens to $m$ and $s$ ?

A particle at $m+sz$ moves with velocity $-a(m+sz)-b$ . Matching the parts with and without $z$ : $m'=-m$ and $s'=-as=\tfrac1s-s$ . So Gaussians stay Gaussian, $m(t)=m_0e^{-t}$ and $(s^2)'=2-2s^2$ , i.e. $s(t)^2=1+(s_0^2-1)e^{-2t}$ . This is the Ornstein–Uhlenbeck flow you will run in the next module.

Check your understanding

What is the Wasserstein gradient of the potential energy $\int V\,d\mu$ at $\mu$ ?

The vector field $\nabla V$ , viewed in $L^2(\mu)$ .
The function $V$ . $V$ is the first variation (the $L^2$ gradient). The Wasserstein gradient is a velocity, so it is $\nabla V$ .
The measure $\nabla V\,\mu$ .That is the flux $v\mu$ in the continuity equation, not the velocity $v$ .

Moving mass by

\mathrm{id}+\varepsilon\eta

changes

\int V\,d\mu

by

\varepsilon\int\langle\nabla V,\eta\rangle\,d\mu+o(\varepsilon)

. The slope is

\|\nabla V\|_{L^2(\mu)}

, and the gradient flow is

\partial_t\mu=\nabla\cdot(\mu\nabla V)

: every particle follows

x'=-\nabla V(x)

independently.

What is the slope of the entropy at $\mu=$ uniform on $[0,1]$ ?

$0$ , because $\rho'=0$ inside the interval.The jumps at 0 and 1 matter: $\rho\notin W^{1,1}_{\mathrm{loc}}(\R)$ . The heat flow spreads them at infinite initial speed.
$+\infty$
$1$ There is no finite subgradient: any finite $\xi$ would make the entropy change at a finite rate under the heat flow, but it drops infinitely fast at first.

Finite Fisher information needs

\rho\in W^{1,1}_{\mathrm{loc}}

. The uniform measure has finite entropy (it is in the domain) but infinite slope; by the regularising effect of Chapter 4, the flow enters the set of finite slope immediately. Draw a box-shaped density in the explorer: smoothing keeps the number finite, but it is large.

For the relative entropy with respect to $\gamma=e^{-V}\mathcal L^d$ (a probability measure), when is the slope zero?

Exactly when $\mu=\gamma$ .
When $\mu$ is a Dirac mass at a minimum of $V$ .A Dirac mass has infinite entropy; it is not in the domain.
Never: the entropy always pushes mass outward.The potential pushes inward. They balance when $\nabla\log\rho=-\nabla V$ .

\xi=\nabla\log(\rho/e^{-V})=0

means

\rho/e^{-V}

is constant on the (connected) support. Choose "Relative entropy" and the "N(0, 1)" preset in the explorer: the arrows vanish.

Practice

The gradient of an interaction energyA first-variation computation

Let $\mathcal W(\mu)=\tfrac12\iint W(x-y)\,d\mu(x)\,d\mu(y)$ with $W$ even and $C^1$ . Compute $\frac{d}{d\varepsilon}\mathcal W\big((\mathrm{id}+\varepsilon\eta)_\#\mu\big)$ at $\varepsilon=0$ and identify $\xi$ .

Solution

$\mathcal W\big((\mathrm{id}+\varepsilon\eta)_\#\mu\big)=\tfrac12\iint W\big(x-y+\varepsilon(\eta(x)-\eta(y))\big)\,d\mu\,d\mu$ . Differentiating gives $\tfrac12\iint\langle\nabla W(x-y),\eta(x)-\eta(y)\rangle$ . Since $\nabla W$ is odd, the two halves are equal, giving $\int\langle(\nabla W*\mu)(x),\eta(x)\rangle\,d\mu(x)$ . So $\xi=\nabla W*\mu$ .

Fisher information of a GaussianAnd the entropy's decay rate

Compute $\int(\rho')^2/\rho\,dx$ for $\rho=N(m,s^2)$ on $\R$ . Along the heat flow $s^2(t)=s_0^2+2t$ , check that $\frac{d}{dt}\mathcal H(\mu_t)=-|\partial\mathcal H|^2(\mu_t)$ .

Solution

$\rho'/\rho=-(x-m)/s^2$ , so $\int(\rho'/\rho)^2\rho\,dx=s^2/s^4=1/s^2$ . With $\mathcal H=-\tfrac12\log(2\pi e s^2)$ , $\frac{d}{dt}\mathcal H=-\tfrac12\cdot\frac{2}{s^2}=-\frac1{s^2}$ . The energy falls at the rate "slope squared", as for any gradient flow.

SimulationAmbrosio–Gigli–Savaré, Ch. 11: Gradient Flows and Curves of Maximal Slope in

\mathscr P_p(X)

Heat and Fokker–Planck by JKO

Everything comes together: the minimizing-movement scheme of Module 2, run in the Wasserstein space with the free energy of Modules 9 and 10, produces the heat equation and the Fokker–Planck equation. Here it runs on particles, one minimization per step.

The idea

Gradient flow in $\mathscr P_2$ (Ch. 11.1). An absolutely continuous curve

\mu_t

whose tangent velocity satisfies

v_t=-\partial^\circ\phi(\mu_t)

(more generally

-v_t\in\partial\phi(\mu_t)

), together with

\partial_t\mu_t+\nabla\cdot(v_t\mu_t)=0

. Under mild conditions this is the same as a curve of maximal slope for

|\partial\phi|

in

(\mathscr P_2,W_2)

.

The JKO scheme. The minimizing movement of Module 2 with

d=W_2

:

\mu^n\in\operatorname*{argmin}_{\mu}\ \phi(\mu)+\frac{W_2^2(\mu,\mu^{n-1})}{2\tau}.

Named after Jordan, Kinderlehrer and Otto, who used it for the Fokker–Planck equation.

Existence and uniqueness (Ch. 11.2). If

\phi

is proper, lower semicontinuous, bounded below on some

W_2

-ball (coercivity) and

\lambda

-convex along generalized geodesics, then for every

\mu_0

in the

W_2

-closure of its domain the JKO scheme converges, the limit is the unique gradient flow, it is characterised by the EVI in

W_2

, and

W_2(\mu_t,\nu_t)\le e^{-\lambda t}W_2(\mu_0,\nu_0)

. The error estimates of Chapter 4 hold as stated there.

With the free energy $\phi(\mu)=\int\rho\log\rho\,dx+\int V\,d\mu$ , Module 10 gives $v=-\nabla\rho/\rho-\nabla V$ , and the continuity equation becomes

\partial_t\rho=\Delta\rho+\nabla\cdot(\rho\nabla V).

$V=0$ gives the heat equation ( $\lambda=0$ ); $V=\tfrac12|x|^2$ gives the Ornstein–Uhlenbeck equation ( $\lambda=1$ ), whose solutions converge exponentially to $N(0,I)$ . Other free energies give the porous medium equation and nonlocal aggregation equations (Ch. 11.2.1).

How the simulation works. On the line, a measure made of $N$ equal particles $x_1<\dots<x_N$ has $W_2^2$ to another such measure equal to $\frac1N\sum|x_i-y_i|^2$ (sorted order is optimal). The entropy is approximated by spreading mass $1/(N-1)$ uniformly over each gap. Each JKO step is then a minimization in $(x_1,\dots,x_N)$ , strictly convex as long as $1/\tau+V''>0$ , solved by Newton's method.

Explore

Potential V

Initial datum

Step τ 0.050

\mu^n

(ticks: particles) exact solution, when known equilibrium

e^{-V}/Z

free energy

\phi(\mu^n)

variance of

\mu^n

exact variance, when known

Worked example

Do one JKO step for the heat equation ( $\phi=\mathcal H$ , $V=0$ ) on $\R$ , starting from $\mu^0=N(0,s_0^2)$ , assuming the minimizer is a centred Gaussian $N(0,s^2)$ .

Write the JKO functional as a function of $s$ .

$W_2^2=(s-s_0)^2$ (Module 7) and $\mathcal H=-\log s+\text{const}$ (Module 9). So minimize $-\log s+\frac{(s-s_0)^2}{2\tau}$ .
Solve for $s_1$ .

The derivative is $-\frac1s+\frac{s-s_0}{\tau}=0$ , i.e. $s^2-s_0s-\tau=0$ , so $s_1=\tfrac12\big(s_0+\sqrt{s_0^2+4\tau}\big)$ .
Compare $s_1^2$ with the exact heat flow, $s^2(\tau)=s_0^2+2\tau$ .

From $s_1^2=s_0s_1+\tau$ and $s_1=s_0+\tau/s_0+O(\tau^2)$ : $s_1^2=s_0^2+2\tau+O(\tau^2)$ . One step is first-order accurate. In fact $\frac{s_1-s_0}{\tau}=\frac1{s_1}$ is implicit Euler for $s'=1/s$ , the exact ODE for the standard deviation.
Why is assuming a Gaussian minimizer harmless here?

The entropy is convex along generalized geodesics, so the JKO functional is strictly convex along them and any critical point is the global minimizer. The Gaussian candidate satisfies the optimality condition $(\boldsymbol t-\mathrm{id})/\tau=\nabla\rho_1/\rho_1$ , where $\boldsymbol t(x)=(s_0/s_1)x$ is the optimal map back to $\mu^0$ : it reads $(s_0/s_1-1)/\tau=-1/s_1^2$ , which is the equation of step 2.

Check your understanding

Which functional has $\partial_t\rho=\Delta\rho+\nabla\cdot(\rho\nabla V)$ as its $W_2$ gradient flow?

$\int\rho\log\rho\,dx+\int V\rho\,dx$
$\tfrac12\int|\nabla\rho|^2dx+\int V\rho\,dx$ The Dirichlet energy gives the heat equation as its $L^2$ gradient flow, not as a $W_2$ one. In $W_2$ it gives a fourth-order equation.
$\int\rho\log\rho\,dx-\int V\rho\,dx$ Check the sign: the velocity is $-\nabla V-\nabla\log\rho$ , so mass flows down $V$ .

\xi=\nabla\log\rho+\nabla V

, and

\partial_t\rho=\nabla\cdot(\rho\,\xi)=\Delta\rho+\nabla\cdot(\rho\nabla V)

. The same PDE is a gradient flow for different pairs (functional, metric); the Wasserstein choice is the one in which the free energy is convex and the flow contracts.

Two solutions of the heat equation on $\R^d$ . What does Chapter 11 give for $W_2(\mu_t,\nu_t)$ ?

$W_2(\mu_t,\nu_t)\le W_2(\mu_0,\nu_0)$
$W_2(\mu_t,\nu_t)\le e^{-t}W_2(\mu_0,\nu_0)$ That needs $\lambda=1$ , as for Ornstein–Uhlenbeck. Two heat flows from translated data stay translates of each other, at constant distance.
It may grow, since diffusion spreads mass.The entropy is 0-convex, so the flow is 0-contracting.

\lambda=0

for the entropy (Module 9, quiz 2). With the potential

\tfrac12|x|^2

added,

\lambda=1

: in the explorer the mean and variance relax to those of

N(0,1)

like

e^{-t}

and

e^{-2t}

.

Can the heat flow start from $\delta_0\in\mathscr P_2(\R)$ , where the entropy is $+\infty$ ?

Yes: $\delta_0$ lies in the $W_2$ -closure of the domain, and the flow is $\mu_t=N(0,2t)$ .
No: the first JKO step needs $\phi(\mu^0)<\infty$ .The step itself is fine: the minimization over $\mu$ only needs $\phi(\mu)<\infty$ for some competitor. Chapter 4's theory covers initial data in the closure of the domain.
Yes, but it stays at $\delta_0$ .The slope term in the energy inequality forces it to move, as in Module 1.

Gaussians

N(0,\varepsilon)

have finite entropy and converge to

\delta_0

in

W_2

. By contraction the flows from them converge, and the limit is the heat kernel

N(0,2t)

, at distance

W_2(\mu_t,\delta_0)=\sqrt{2t}

.

Practice

Exponential contraction for Ornstein–UhlenbeckChecking λ = 1 by hand

With $m(t)=m_0e^{-t}$ and $s(t)^2=1+(s_0^2-1)e^{-2t}$ (Module 10), verify $W_2(\mu_t,\gamma)\le e^{-t}W_2(\mu_0,\gamma)$ for $\gamma=N(0,1)$ .

Hint

$W_2^2(\mu_t,\gamma)=m(t)^2+(s(t)-1)^2$ . Write $s-1=(s^2-1)/(s+1)$ .

Solution

The mean term is $m_0^2e^{-2t}$ . For the other, $|s(t)-1|=\frac{|s_0^2-1|e^{-2t}}{s(t)+1}$ , and we need this $\le e^{-t}|s_0-1|$ , i.e. $s(t)+1\ge(s_0+1)e^{-t}$ . Since $s(t)^2\ge s_0^2e^{-2t}$ (expand) we have $s(t)\ge s_0e^{-t}$ , and $1\ge e^{-t}$ . Adding the two terms gives the claim.

The porous medium equationA different internal energy

Show that the $W_2$ gradient flow of $\mathcal F(\mu)=\frac1{m-1}\int\rho^m\,dx$ ( $m>1$ ) is $\partial_t\rho=\Delta(\rho^m)$ .

Solution

The first variation is $\frac{m}{m-1}\rho^{m-1}$ , so $\xi=\nabla\big(\frac{m}{m-1}\rho^{m-1}\big)=m\rho^{m-2}\nabla\rho$ . Then $\partial_t\rho=\nabla\cdot(\rho\,\xi)=\nabla\cdot(m\rho^{m-1}\nabla\rho)=\Delta(\rho^m)$ . McCann's condition $m\ge1-1/d$ makes $\mathcal F$ displacement convex, so Chapter 11's theory applies.