Uncategorized


This is the follow up to this post on the completion of the space of Radon measures with respect to transport norm. In the that post we have seen that

\displaystyle \mathrm{KR}_0(X)^*\cong \mathrm{Lip}_0(X),

i.e. that the completion of the Radon measure with zero total mass with respect to he dual Lipschitz norm

\displaystyle \|\mu\|_{\mathrm{Lip}_0}^* = \sup\{\int f{\mathrm d}\mu\ :\ \mathrm{Lip}(f)\leq 1,\ f(e)=0\}

where {e\in X} is some base point in the metric space {X}.

Recall that on a compact metric space {(X,d)} we have {\mathfrak{M}(X)}, the space of Radon measures on {X}. The Kantorovich-Rubinstein norm for measure is defined by

\displaystyle \|\mu\|_{\mathrm{KR}} = \sup\{\int f{\mathrm d} \mu\ :\ \mathrm{Lip}(f)\leq 1,\ \|f\|_\infty\leq 1\}.

Theorem 1 For a compact metric space {(X,d)} it holds that

\displaystyle \mathrm{KR}(X)^* \cong \mathrm{Lip}(X).

Proof: We give an explicit identification for {\mathrm{KR}(X)^*} as follows:

  1. Define a Lipschitz function from an element of {\mathrm{KR}(X)^*}: For every {\phi\in\mathrm{KR}(X)^*} and {x\in X} we set

    \displaystyle (T\phi)(x) = \phi(\delta_x).

    Now we check that by linearity and continuity of {\phi} that for any {x\in X} it holds that

    \displaystyle |(T\phi)(x)| = |\phi(\delta_x)|\leq \|\phi\|\|\delta_x\|_{\mathrm{KR}} = \|\phi\|.

    This shows that {T\phi:X\rightarrow {\mathbb R}} is a bounded function. Similarly for all {x,y\in X} we have

    \displaystyle |(T\phi)(x)-(T\phi)(y)| = |\phi(\delta_x-\delta_y)|\leq \|\phi\|\|\delta_x-\delta_y\|_{\mathrm{KR}}\leq \|\phi\|\min(2,d(x,y))\leq \|\phi\|d(x,y).

    This shows that {(T\phi)} is actually Lipschitz continuous, and moreover, that {T:\mathrm{KR}(X)^*\rightarrow\mathrm{Lip}(X)} is continuous with norm {\|T\|\leq 1}.

  2. Define an element in {\mathrm{KR}(X)^*} from a Lipschitz function: We just set for {f\in\mathrm{Lip}(X)} and {\mu\in\mathfrak{M}(X)}

    \displaystyle (Sf)(\mu) = \int_Xf{\mathrm d}\mu.

    By the definition of the {\mathrm{KR}}-norm we have

    \displaystyle |(Sf)(\mu)\leq \|f\|_{\mathrm{Lip}}\|\mu\|_{\mathrm{KR}},

    which shows that {S(f)} can be extended to a continuous and linear functional {S:\mathrm{KR}(X)\rightarrow{\mathbb R}}, i.e. {Sf\in\mathrm{KR}(X)^*}, and we also have that {\|S\|\leq 1}.

  3. Check that {S} and {T} invert each other: Finally we check that {T} and {S} are inverses of each other. We begin with {TS}: For {x\in X} and {f\in\mathrm{Lip}(X)} observe that

    \displaystyle T(Sf)(x) = Sf(\delta_x) = \int_X f{\mathrm d}\delta_x = f(x)

    i.e. {TS} is the identity on {\mathrm{Lip}(X)}. Conversely, for any {\phi\in\mathrm{KR}(X)^*} and {x\in X} we check

    \displaystyle S(T\phi)(\delta_x) = \int_X T\phi{\mathrm d}\delta_x = (T\phi)(x_0) = \phi(\delta_x).

    By density of the Dirac measures in {\mathrm{KR}(X)} we conclude that indeed {ST\phi = \phi}, i.e. {ST} is the identity on {\mathrm{KR}(X)^*}.

\Box

In this post, the first of two related ones, I describe the closure of the space of Radon measures with zero total mass with the respect to the Kantorovich-Rubinstein norm. Somebody asked me what this was after some talk – I did not know the answer and couldn’t figure it out, so I asked this over on mathoverflow, got the right pointers, and here’s the post. A great deal of the post comes from the book Lipschitz Algebras by Nik Weaver (the very same Nik Weaver who answered over at MO) but beware that the notation is slightly different in this post (especially the usage of {\mathrm{KR}}).

1. The Kantorovich-Rubinstein norm on the space of Radon measures

Let {(X,d)} be a metric space and denote by {\mathfrak{M}(X)} the space of Radon measures on {X}. We will work with compact {X} throughout this post, although in many places compactness is not needed. Following Bourbaki we say that the space {\mathfrak{M}(X)} is defined as the dual of the space {C(X)} of continuous functions on {X}, equipped with the supremum norm. The dual pairing of a measure {\mu} and a continuous function {f} is then

\displaystyle  \langle \mu,f\rangle = \int_X f{\mathrm d} \mu

(and the integral can also be understood in terms of standard measure theory where a measure is defined by a set function of a {\sigma}-algebra). The norm of {\mathfrak{M}(X)} is

\displaystyle  \|\mu\|_{\mathfrak{M}} = \sup\{\int_X f{\mathrm d}\mu\ :\ \|f\|_\infty\leq 1\}

and is called variation norm or Radon norm (sometimes also total variation, not to be confused with the seminorm on the space of functions with bounded variation with a similar name). The variation norm captures some of the topological structure of {X} but does not take into account the metric structure of {X} (in fact, in can be defined on compact topological spaces {X}).

One can define further norms and semi-norms on {\mathfrak{M}(X)} and subspaces thereof and two of them that are particularly suited to capture the underlying metric structure of {X} are:

  1. The dual Lipschitz-norm

    \displaystyle  \|\mu\|_{\mathrm{Lip}_0}^* = \sup\{\int f{\mathrm d} \mu\ :\ \mathrm{Lip}(f)\leq 1\}

    gives finite values on the closed subspace {\mathfrak{M}_0(X)} of measures with total mass equal to zero, i.e. {\mu(X)=0}.

  2. The Kantorovich-Rubinstein norm

    \displaystyle  \|\mu\|_{\mathrm{KR}} = \sup\{\int f{\mathrm d} \mu\ :\ \mathrm{Lip}(f)\leq 1,\ \|f\|_\infty\leq 1\}

    gives finite values for all Radon measures.

Actually, it is not totally trivial to show that these are indeed norm but also not too hard (you may look up this fact for {\mathrm{Lip}_0^*} in Proposition 2.3.2 in the above mentioned book Lipschitz Algebras and the case of {\mathrm{KR}} is basically similar).

Obviously {\|\mu\|_{\mathrm{KR}}\leq \|\mu\|_{\mathfrak{M}}}. The reversed inequality is not true and also does not even hold up to a constant if {X} has a non-constant convergent sequence. This can be seen by observing that for {x\neq y} one has {\|\delta_x - \delta_y\|_{\mathfrak{M}} = 2} while {\|\delta_x - \delta_y\|_{\mathrm{KR}} = \|\delta_x-\delta_y\|_{\mathrm{Lip}_0}^* \leq d(x,y)}.

While {(\mathfrak{M}(X),\|\cdot\|_{\mathfrak{M}})} is a Banach space (by its very definition as a dual space) it is not a priori clear if {(\mathfrak{M}(X),\|\cdot\|_{\mathrm{KR}})} is also a Banach space. In fact, it is clear that it is not:

Theorem 1 The space {(\mathfrak{M}(X),\|\cdot\|_{\mathrm{KR}})} is complete if and only if {X} is finite, similarly for {(\mathfrak{M}_0(X),\|\cdot\|_{\mathrm{Lip}_0}^*)}.

Proof: Let {X} be finite with {n} elements, say. Then {\mathfrak{M}(X)} is naturally identified with {{\mathbb R}^n} and there all norm are equivalent, which shows completeness with all norms. Now let {X} be infinite. Since {X} is also compact, there are, for every {\epsilon>0} two points {x,y\in X} with {d(x,y)<\epsilon}. For these points we’ve already observed that {\|\delta_x - \delta_y\|_{\mathrm{KR}} <\epsilon} while {\|\delta_x - \delta_y\|_{\mathfrak{M}} = 2}. This shows that the identity {(\mathfrak{M}(X),\|\cdot\|_{\mathfrak{M}}) \rightarrow (\mathfrak{M}(X),\|\cdot\|_{\mathrm{KR}})} is a continuous linear bijection but does not have a continuous inverse. So the open mapping theorem shows that {(\mathfrak{M}(X),\|\cdot\|_{\mathrm{KR}})} can not be complete. The argument for {(\mathfrak{M}_0(X),\|\cdot\|_{\mathrm{Lip}_0}^*)} is the same. \Box

This raises two related questions:

  1. What is the completion of the space of Radon measures {\mathfrak{M}(X)} with respect to Kantorovich-Rubinstein norm {\|\cdot\|_\mathrm{KR}}?
  2. What is the completion of the space of Radon measures with zero mass {\mathfrak{M}_0(X)} with respect to the dual Lipschitz norm {\|\cdot\|_{\mathrm{Lip}_0}^*}?

In this post we’ll see the answer to the second question.

Note that the proof above indicates some important phenomenon: Diracs with opposite signs that are getting closer seem to be a particular thing here. Indeed, if {x_k} and {y_k} are two sequences in {X} with {x_k-y_k\rightarrow 0} then for

\displaystyle  \mu_k = \delta_{x_k} - \delta_{y_k}

it holds that {\|\mu_k\|_{\mathrm{KR}}\leq d(x_k,y_k)\rightarrow 0} (similarly for {\|\cdot\|_{\mathrm{Lip}_0}^*}) but {\mu_k} is not converging to zero with respect to {\|\cdot\|_{\mathfrak{M}}}. It holds that {\mu_k} does converge weakly to zero if {x_k} (and hence {y_k}) does converge to something, but in the case that {x_k} (and hence {y_k}) does not converge, {\mu_k} does not even converge weakly.

We’ll come to a description of the completion in a minute but first we introduce several notions that will be used.

2. Spaces of Lipschitz functions

For a compact metric space {(X,d)} we say that {f:X\rightarrow{\mathbb R}} is Lipschitz continuous if it has finite Lipschitz-constant

\displaystyle  \mathrm{Lip}(f) = \sup_{x\neq y}\frac{|f(x)-f(y)|}{d(x,y)}.

The theorem of Arzela-Ascoli shows that the space {\mathrm{Lip}(X)} of all Lipschitz continuous functions is a Banach space, when equipped with the norm

\displaystyle  \|f\|_{\mathrm{Lip}} = \max(\|f\|_\infty,\mathrm{Lip}(f)).

If we additionally mark a distinguished base point {e\in X} we can also consider the space

\displaystyle  \mathrm{Lip}_0(X) = \{f\in \mathrm{Lip}(X)\ :\ f(e)=0\}.

On this space the Lipschitz constant itself is a norm (and not only a semi-norm) and we denote it by

\displaystyle  \|f\|_{\mathrm{Lip}_0} = \mathrm{Lip}(f).

In fact the spaces {\mathrm{Lip}} and {\mathrm{Lip}_0} are really closely related since in the case of metric spaces of finite diameter one space can be turned into the other and vice versa. The idea is to enhance a given metric space {X} with an additional base point that we put in some way “right in the middle of {X}” or, maybe more accurately, “at equal distance of anything” as follows:

Theorem 2 For a compact metric space {(X,d)} (with no special base point) and diameter {\mathrm{diam}(X) = D} denote {X^+ := X\cup\{e\}} for some new point {e} and let {d^+:X^+\times X^+\rightarrow{\mathbb R}} be equal to {d} on {X} and satisfy {d^+(x,e)=D/2} for all {x\in X}. Then:

  1. {(X^+,d^+)} is a compact metric space with diameter {\mathrm{diam}(X^+)=D}.
  2. For {f\in\mathrm{Lip}(X)} define {f^+\in \mathrm{Lip}_0(X^+)} by {f^+(x) = f(x)} for {x\in X} and {f^+(e)=0}. Then the mapping {T:f\mapsto f^+} is a homeomorphism from {\mathrm{Lip}(X)} to {\mathrm{Lip}_0(X^+)}.

Proof:

  1. The only thing to check for {d^+} to be a metric is that {d^+} also fulfills the triangle inequality: but since for {x,y\in X} it holds that {d^+(x,e)+d^+(e,y) = D/2 + D/2 = D\geq d(x,y) = d^+(x,y)} this is fulfilled.
  2. Let {f\in \mathrm{Lip}(X)}. Then

    \displaystyle  \frac{|f^+(x)-f^+(e)|}{d^+(x,e)} = \frac{|f(p)-0|}{D/2}\leq \frac2D\|f\|_\infty \leq \frac2D\|f\|_{\mathrm{Lip}}

    and consequently

    \displaystyle  \mathrm{Lip}(f^+) \leq\tfrac2D\|f\|_{\mathrm{Lip}}.

    On the other hand for all {x\in X}

    \displaystyle  |f(x)| = \frac{D}{2}\frac{|f(x)-0|}{D/2}\leq \frac{D}2\mathrm{Lip}(f^+)

    which shows {\|f\|_\infty\leq\tfrac{D}2\mathrm{Lip}(f^+)}. Obviously we have {\mathrm{Lip}(f)\leq \mathrm{Lip}(f^+)}, which finishes the argument.

\Box

3. The Arens-Eells space

That spaces of Lipschitz functions should play a role for the {\mathrm{KR}}– and {\mathrm{Lip}_0^*}-norm seems pretty obvious—Lipschitz functions are used it the very definition of the norm. Now we come to some space for which the relation with the {\mathrm{KR}}– and {\mathrm{Lip}_0^*}-norm may not be that obvious but which is indeed very much related.

Definition 3 For a compact metric space {(X,d)} we define a molecule as a function {m:X\rightarrow{\mathbb R}} with finite support with {\sum_{x\in X} m(x)=0}.

Obviously, the set of molecules is a linear space.

Any molecule can be identified with a measure on {X} as follows: For a molecule {m} define a measure

\displaystyle  \mu_m = \sum_{x\in X} m(x)\delta_{x}.

In other words: At every point {x} of the support of {m} we put a delta with weight {m(x)}.

Since the support of {m} is finite, the sum is actually finite and in addition, this measure {\mu_m} has zero total measure since

\displaystyle  \mu_m(X) = \sum_{x\in X}m(x)\delta_{x}(X) = \sum_{x\in X}m(x)=0.

So one may say that the linear space of all molecules is naturally identified with the linear space of all finite linear combinations of deltas with zero total mass.

On the space of molecules we define the so-called Arens-Eells norm. To do so we introduce elementary molecules consisting having a two-element support with values {\pm 1} on them, namely for {x,y\in X}

\displaystyle  m_{xy}(z) = \begin{cases} 1, & z=x\\ -1, & z=y\\ 0, & \text{else.} \end{cases}

Note that any molecule {m} can be written as finite linear combination of elementary molecules. (To do so you may order the support of some given {m} as {\{x_1,\dots x_n\}}, start with {m(x_1)m_{x_1 x_2}}, then form {m^1 = m - m(x_1)m_{x_1x_2}}, observe that {m^1} has a support of size {n-1}, and proceed iteratively as started). Importantly, the decomposition of a molecule into elementary molecules is not unique.

Definition 4 For a molecule {m} on {X} we set

\displaystyle  \|m\|_{\AE} = \inf\{\sum_{i=1}^n |a_i|d(x_i,y_i)\ :\ m = \sum_{i=1}^n a_i m_{x_iy_i}\}

where the infimum is taken over all decomposition of {m} into elementary molecules.

Actually, it is not clear from the start that {\|\cdot\|_{\AE}} is indeed a norm. While homogeneity and the triangle inequality are more or less straight forward, definiteness is not clear from the beginning. We will see that in a minute, but it makes sense to first introduce the completion of the space of molecules with respect to the (semi-)norm {\|\cdot\|_{\AE}} since its dual is indeed familiar. Since we do not know yet that {\|\cdot\|_{\AE}} is a norm, we have to be careful with the completion:

Definition 5 The Arens-Eells space {\AE(X)} on a compact metric space is the completion of the space of molecules with respect to the seminorm {\|\cdot\|_{\AE}} modulo elements with zero norm.

The great thing is that the dual of {\AE(X)} is a well known space:

Theorem 6 For a compact metric space {(X,d)} with some base point {e} it holds that

\displaystyle  \AE(X)^* \cong \mathrm{Lip}_0(X).

On bounded sets, weak* convergence in {\mathrm{Lip}_0(X)} agrees with pointwise convergence.

Proof: We represent elements of {\AE(X)^*} as Lipschitz functions by the mapping {T_1:\AE(X)^*\rightarrow \mathrm{Lip}_0(X)} be setting for {\phi\in \AE(X)^*} and {x\in X}

\displaystyle  (T_1\phi)(x) = \phi(m_{xe})

Note that {(T_1\phi)(e) = \phi(m_{ee}) = 0}. By the definition of {\|\cdot\|_{\AE}} it holds that {\|m_{xy}\|_{\AE}\leq d(x,y)} and hence,

\displaystyle  |(T_1\phi)(x)-(T_1\phi)(y)| = |\phi(m_{xe} - m_{ye})| = |\phi(m_{xy})|\leq \|\phi\|d(x,y)

which shows that {\mathrm{Lip}(T_1\phi)\leq \|\phi\|} and we conclude that {T_1\phi\in\mathrm{Lip}_0(X)} and also that {\|T_1\|\leq 1}. Conversely, we now define a map that associates to every Lipschitz function vanishing at the base point an element in {\AE(X)^*}: Define {T_2:\mathrm{Lip}_0(X)\rightarrow \AE(X)^*} for any molecule {m} and any {f\in \mathrm{Lip}_0(X)} by

\displaystyle  (T_2f)(m) = \sum_{x\in X} f(x)m(x).

Note that for a decomposed molecule {m = \sum_{i=1}^n a_i m_{x_iy_i}} we have

\displaystyle  \begin{array}{rcl}  |(T_2 f)(m)| & =&|(T_2 f)(\sum_{i=1}^n a_i m_{x_iy_i})\\ & \leq & \sum_{i=1}^n |a_i| |(T_2 f)(m_{x_iy_i})|\\ & = &\sum_{i=1}^n |a_i| |f(x_i) - f(y_i)|\\ & \leq & \mathrm{Lip}(f) \sum_{i=1}^n |a_i| d(x_i,y_i). \end{array}

Taking the infimum over all decompositions, we conclude {|(T_2 f)(m)|\leq \mathrm{Lip}(f)\|m\|_{\AE}} showing that {T_2 f\in \AE(X)^*} and {\|T_2f\|\leq\mathrm{Lip}(f)}, i.e, {\|T_2\|\leq 1}. Now let’s look at {T_1T_2}: For {x\in X} and {f\in\mathrm{Lip}_0(X)} it holds that {T_1(T_2 f)(x) = (T_2 f)(m_{xe}) = f(x) - f(e) = f(x)}, i.e. {T_1T_2 = I}. Also for {\phi\in \AE(X)^*} and a molecule {m}: {T_2(T_1\phi)(m) = \sum_{x\in X}(T_1\phi)(x)m(x) = \sum_{x\in X}\phi(m_{xe})m(x) = \phi(\sum_{x\in X}m(x)m_{xe})= \phi(m)}. So {T_2} and {T_1} are indeed inverses and hence provide identifications of {\AE(X)^*} and {\mathrm{Lip}_0(X)}. Now consider a sequence of function {f_n\in \mathrm{Lip}_0(X)} that converges weakly* to {f}. This says that (in the notation above) for any molecule {m} it holds that {(T_2f_n)(m)\rightarrow (T_2 f)(m)}. Particularly for the molecules {m_{xe}} we have

\displaystyle  (T_2 f_n)(m_{xe}) = \sum_{y\in X} f_n(y)m_{xe}(y) = f_n(y).

It follows that {f_n(x)\rightarrow f(x)} for all {x}. This shows that weak* convergence implies pointwise convergence. If, conversely, {f_n} converges pointwise, we conclude that {(T_2 f_n)(m_{xe}) \rightarrow (T_2 f)(m_{xe})} for all {m_{xe}}. By definition, these are dense in {\AE(X)} and since we assume that the {f_n} are bounded by assumption, this implies weak* convergence. \Box

The above proof also shows that {\|\cdot\|_{\AE}} is indeed a norm and moreover, that it can be written as

\displaystyle  \|m\|_{\AE} = \sup\{\sum_{x\in X} f(x)m(x)\ :\ f(e)=0,\ \mathrm{Lip}(f)\leq 1\}

(also, by Arzela-Ascoli, there is a Lipschitz function {f} with {\mathrm{Lip}(f)\leq 1} and {f(e)=0} where the supremum is attained, but we will not need this). This shows the following fact:

Corollary 7 For any molecule {m} on a compact metric space {X} with base point {e} and the corresponding measure {\mu_m} it follows that

\displaystyle  \|m\|_{\AE} = \|\mu_m\|_{\mathrm{KR}}.

4. The completion of {\mathfrak{M}_0(X)} under the dual Lipschitz norm

Now we come to the answer of the second question posed in the beginning. We define by {\mathrm{KR}_0(X)} the completion of {\mathfrak{M}_0(X)} (the space of Radon measures with zero total mass) with respect to {\|\cdot\|_{\mathrm{Lip}_0}^*} and aim at a characterization of this space.

Theorem 8 It holds that {\AE(X)\cong \mathrm{KR}_0(X)} isometrically.

Proof: We first show that any measure {\mu} on {X} with zero total mass can be approximated in the {\mathrm{Lip}_0^*}-norm by measures {\mu_m} defined my molecules {m}. So let {\epsilon>0} and {\mu\in \mathrm{KR}_0(X)}. We set {\epsilon' = \epsilon/\|\mu\|_{\mathfrak{M}}}. Now we cover {X} by an {\epsilon'}-net, that is, we take {x_1,\dots,x_n} such that balls {B_k} around {x_k} with radius {\epsilon'} cover {X}. From this cover we define by {V_1=U_1}, {V_k = U_k\setminus(U_1\cup\cdots\cup U_{k-1})} a disjoint cover of {X} (i.e. a partition). Now we define a molecule {m} by

\displaystyle  m(x) = \left\{ \begin{array}{ll} \mu(V_k), & \text{if}\ x=x_k\\ 0, & \text{else.} \end{array} \right.

Clearly {m} is a molecule (its support is the {n} point {x_k} and the sum {\sum_{x}m(x)} equals {\mu(X)=0}). To see that {\mu_m} approximates {\mu} in the {\mathrm{Lip}_0^*}-norm we start as follows: For any function {f} with {\mathrm{Lip}(f)\leq 1} we see

\displaystyle  \begin{array}{rcl}  |\int_{V_k}f{\mathrm d}(\mu-\mu_m)| &=& |\int_{V_k} f{\mathrm d}\mu - \int_{V_k}f{\mathrm d}\mu_m|\\ &=& |\int_{V_k} f{\mathrm d}\mu - f(x_k)\mu(V_k)|\\ &=& |\int_{V_k} (f-f(x_k)){\mathrm d}\mu|\\ &\leq& |\int_{V_k} \mathrm{Lip}(f)\epsilon'{\mathrm d}\mu| = \epsilon'\|\mu\|_{\mathfrak{M}(V_k)}. \end{array}

Summing this over {k} we get for every {f} with {\mathrm{Lip}(f)\leq 1}

\displaystyle  |\int_X f{\mathrm d}(\mu-\mu_m)|\leq \epsilon'\|\mu\|_{\mathfrak{M}} = \epsilon.

Taking the supremum over these {f} gives {\|\mu-\mu_m\|_{\mathrm{Lip}_0}^*\leq \epsilon} as desired. Corollary 7 shows that {\|m|\|_{\AE}=\|\mu_m\|_{\mathrm{Lip}_0}^*} and from the above we see that these measures are dense in {\mathrm{KR}_0(X)}. Hence, the correspondence {m\mapsto\mu_m} is an isometry on dense subsets of {\AE(X)} and {\mathrm{KR}_0(X)} which proves the assertion. \Box

Finally, we come to the announced description of the space {\mathrm{KR}_0(X)} (defined as completion of {(\mathfrak{M}_0(X),\|\cdot\|_{\mathrm{Lip}_0}^*)}): It is equal to the Arens-Eells space and hence, its dual space is the space of Lipschitz functions rooted on a base point.

Corollary 9 For a compact metric space {(X,d)} with basepoint it holds that

\displaystyle  \mathrm{KR}_0(X)^*\cong\mathrm{Lip}_0(X).

To conclude this post, I just mention that the techniques used above are related to the Kuratowski embedding and the related Kuratowski–Wojdysławski embedding that embed metric spaces into certain Banach spaces.

Do you remember free time as a kid that you wasted with connecting dots? If you actually liked it, here’s some good news: There are dot-to-dot books for grown-ups! Most notable, there are the books by Thomas Pavitte with great pictures with 1000 dots.

So, these are some of the books

and here is some video:

 

Actually, it takes some time to connect 1000 dots; I need ten minutes or so, depending a bit an the picture.

For the fun of it, I coded some lines in MATLAB to connect the dots automatically. And since I am a lazy programmer, I did not bother to connect the dots in the manner that was prescribed by the artist but more efficiently:

1. Greedy paths

For the greedy path, we start at some randomly chosen dot and connect the dot where we are with the closest possible dot where we haven’t been already.

Here’s how this looks for one of Thomas’ pictures:

201602040822-greedy-crop

2. Shortest paths

The greedy path sometimes makes very large jumps (when it runs into some corner, using all the dots in the vicinity). This leads to some spurious large jumps in the picture. In used some simple heuristics to find some “locally shortest paths” through the thousand dots. (And “locally shortest” means that there are no two edges for which swapping improves the total lengths of the paths.) Actually, I started out with the goal to solve the travelling salesman problem over the thousand dots, i.e., to find the shortest path of all. Then it turned out that

  1. Solving the travelling salesman problem is not that simple to solve – well it’s one of the best investigated NP-hard optimization problems and there is no doubt that it would take my laptop only little time to solve it with 1000 dots if fed with the right code.
  2. The locally shortest path already looks quite appealing and I am not sure how the shortest path would look any different.

Here is the locally shortest path:

201602040822-tspheuristic-crop.png

Oh, by the way: the image is a pug dog, the one that you can party see on this cover

Here are some more pictures (not by Thomas Pavitte). Middle is the greedy, right the locally shortest path:

This slideshow requires JavaScript.

Since the Wikipedia page of the travelling salesman problem contains a formulation as an integer linear program to solve it, I may give it a try in the future…

Today I learned that Ernie Esser passed away on March 8th, 2015 at age 34. Ernie was a PostDoc at UBC, Vancouver (PhD from UCLA) and worked in applied mathematics, especially imaging, optimization and inverse problems. I can’t say that I knew him very well – but we were in the similar research communities and I remember sitting with him in restaurants and chatting at several occasions (e.g. in Vancouver and Hong Kong…) and I remember him as a perticularly nice guy. Also I followed his work and it frequently happened that I found papers by him thinking “ok, that’s solved” crossing a problem from the list of thing I would have liked to work on.

I am seriously shocked to learn that he died from pneumonia, especially at his young age. There is a obituary weblog here and I am glad that his workgroup did not only set up this page but also plans to do a scientific event to recognize his work.

A quick post to keep track of several things:

This is the last post in a series of posts (which was not intended to be a series). The series started with this post in which I reported some experience with job interviews I had in spring last year, and continued with this post which told what happened afterwards. The story ended with the paragraph “Now the final steps will be: Preparation of the next list of wishes, negotiations to stay and finally, the most difficult part, forming a well-founded decision.” That was about eleven month ago and was not totally wrong. Here is what happened then:

1. The Bleibeverhandlung

The Bleibeverhandlung (the negotiations to stay) is in principle similar to the negotiations with other universities. But there are important differences: The first one is due to the fact that there has been no official committee of the department involved so far and hence, the department has to form an opinion on how much they want to keep you. As far as I know this usually happens in an informal way and can be very different in different places and also the dean (or, in my case, the “speaker of the department”) may handle this in its own way. Also, you will not be involved in this step in any way (I think). The amount of support you get is crucial for the next steps. The department has to report its opinion to the dean (who is basically in control of the money here) and the dean has to decide about a strategy how to keep you (if your support is strong enough). Again, this is very different in different cases. Also, I do not know too much about this process, but at least there will be some communication between the dean and the president (or their offices). But after this procedure, the next steps of negotiations are basically the same as before: First negotiations with the dean, then with the president. Again, the first negotiation is somehow more important as many things are handled by the dean. In my case there was the question on which kind of position the department could keep me and how it could be arranged to fill this position with me. I have been Juniorprofessor (basically equal to assistant professor) and according to German law, there is not way of promotion to the “next level”. The university had to find an “open position for a professor”. But there was such a position (which I knew before since I had a tenure track position). The next obstruction was that, again according to German law, there usually has to be an official public announcement if such a position is to be filled. Consequently, anyone who is qualified could apply and should have a positive probability to get the job. However, I learned that my state has the possibility to fill a position without public announcement and it was part of my offer that my university “offered to start the initiation of this procedure”. It is somehow difficult to translate but the university could not even offer to initiate this “filling without public announcement” because this is something on which several committees has to agree.

2. The decision

Well, I had the official offer of my university pretty quick after negotiations. Basically, it was on par with the other offers (slightly better in some respects, slightly worse in others – but clearly no clear winner). The only caveat was, that there was no guarantee that I could get a permanent position because this depended on the decision of more committees. However, I had a formal statement that the president and the dean would initiate and support the procedure. Moreover, colleagues told me that my university had done a great job in keeping its promises in similar respects.

So, the decision was not easy. However, I decided not to play “ping-pong” with the other universities (which could be possible – but I can not tell you how that works) and to decide on basis of the facts I had after one round of negotiations. It was a tough and close decision which I do not comment in more detail here. But I decided to stay at TU Braunschweig.

3. Another application

Correct: I had to write another application! Although the process to “fill the position without public announcement” was granted by all committees (which took quite some time), that still meant that there had to be a normal procedure for an appointment: A committee had to be formed which had to agree on criteria for the position and had to ask me to apply for the position. Then, I applied and I even were invited to give a talk, a test lecture and had a job interview (all at my own university). Usually, there also had to be external referee reports but somebody found that there was the possibility to have enough external committee members present at the presentation and the job interview who then have their opinion recorded. After that, the committee had to form a decision and a one person list which went the usual way through administration. Then I got the offer in the official way and was even asked for another negotiations. But since the university really had realized the whole procedure totally as promised, I did not see any reason to insist on further negotiations. They had done anything as we had agreed on, and so I just said, that I agree to take the position on the basis of the offer they had formulated. This went smoothly and I accepted (officially by mail). The next step was that I had to go to the Amtsarzt (translates to “public health officer”) who had to check if was healthy enough for a lifetime professorship. (I had been at the Amtsarzt before I started my Juniorprofessorship, but then he only checked if I was healthy enough for six years…). Also, this went smoothly and a few days ago there was my “appointment for life”. (Last remark: I wondered that I did not had to repeat the “official oath” (Amtseid) because I had done this when I started the Juniorprofessorship, and this remains a lifetime.)

End of the story – indeed a happy end for me. The procedure was quite slow – but as far as I’ve heard all the people who have been involved did their best to make the procedure as quick as possible and I am very thankful for the effort and support of many people. It is just an awfully complicated procedure to appoint a professor in Germany which consists of many steps and many people and committees are involved…

This time I have something which is very specific for the German academic system and it seems to me that writing in German is more appropriate here.

Die Berufung von Professoren ist ein aufwändiges und langwieriges Unterfangen. Es gibt viele Regeln zu beachten und viele Meinungen und Daten fließen ein. Insgesamt soll “der/die beste Kandidat/in” die Stelle bekommen. Die Entscheidung basiert am Ende auf dem Votum der Kommission die sich ihre Meinung auf Grund der Eckdaten der Bewerbung und des Lebenslaufes, des persönlichen Eindrucks bei der Vorstellung und auf dem Votum externer Gutachter bildet. Das alles kostet viel Zeit und Arbeit. Außerdem kann das ganze Verfahren schnell unter den Verdacht kommen, dass persönliche Beziehungen eine zu große Rolle spielen könnten und dass am Ende nicht immer “der/die Beste” genommen wird (obwohl es umfangreiche Regeln zum Ausschluss von Befangenheit gibt). Man stelle sich vor, es gäbe eine zentrale Stelle, die mit viel Aufwand und geschultem Personal Daten über Nachwuchswissenschaftler sammelt:

  • Wer hat was publiziert? Wer wird wie oft zitiert?
  • Wer trägt auf welchen Konferenzen und Workshops vor? Und wer wird von wem eingeladen?
  • Was denken die führenden Köpfe, wer die großen Nachwuchstalente sind? Was denken die Nachwuchskräfte über sich gegenseitig?
  • Wer hat wieviel Drittmittel eingeworben? Wer hat welche Kooperationen initiiert und welche Patente angemeldet?

All das lässt sich durch eine zentrale und unabhängige Stelle viel effizienter und auch viel objektiver erheben. Eine Berufungskommission könnte sich dann einfach und schnell eine fundierte Meinung bilden. Eine einfache Datenbankanfrage an die zentrale Stelle würde sofort eine Auskunft liefern, wer von den Kandidaten am besten da steht und die Auswahl aus den oft über fünfzig Bewerbungen wäre kaum noch Arbeit…

Würde das Verfahren funktionieren? Würde irgendjemand das Verfahren akzeptieren? Die Antwort auf diese rhetorischen Fragen fällt eindeutig aus: Eine solche zentrale Stelle wäre völliger Schwachsinn und die Informationen, die sie liefern könnte wären nutzlos. Einerseits sind die Kriterien sicherlich nicht gut gewählt: Publikationen in der “wissenschaftlichen Vanity-Press” zählen gleich viel wie ein Artikel in den Annals? Was ist mit interdisziplinären Arbeiten, die in leicht “fachfremnden” Zeitschriften erscheinen? Einladungen auf Konferenzen lassen sich durch Gegeneinladung erschleichen. Eine gute Reputation bekomme ich nur, wenn ich mich Gut-Freund mit den wichtigen Leuten mache – gute “Netzwerker” haben da natürlich einfacher, als “stille Wasser”. Man könnte natürlich versuchen, bei den Kriterien nachzubessern: Wir beziehen die Reputation einer Zeitschrift mit ein! Wir checken “Gegeneinladungen” und rechnen sie wieder heraus! Wir beziehen auch Zeitschriften in “angrenzenden Feldern” mit ein! Man merkt schnell, dass auch das Nachbessern zum Scheitern verurteilt ist: Wer legt denn die Reputation einer Zeitschrift fest? Gegeneinladungen sind nicht immer ein Zeichen von Gemauschel, sondern oft ganz natürlich und Ausdruck einer Kooperation. Welche Felder grenzen denn an und wo wird dann die Grenze gezogen?

Außerdem ist eine solche zentrale Stelle auch fundamental in Frage zu stellen: Ist es überhaupt machbar, Kandidaten neutral und objektiv zu Bewerten? Und was soll “objektiv” bedeuten, wenn doch jeder Lebenslauf verschieden und die Anforderungen an jede Stelle und an jeder Uni verschieden sind? Eine anerkannte, allgemeingültige Methode, um Kandidaten gegeneinander abzuwägen gibt es nicht. Eine standardisierte, zahlenbasierte Bewertung von Personen ist absurd. Eine derart komplexe Thematik lässt sich nicht durch ein automatisches Verfahren und einfach in Zahlen abbilden. Vom ethischen Aspekt ganz zu schweigen…

Schon mal was vom CHE Uni-Ranking gehört?

Next Page »

Follow

Get every new post delivered to your Inbox.

Join 81 other followers