### view poster.tex @ 15:1cb388196827

Change of layout
author Benedikt Fluhr Mon, 17 Apr 2017 20:37:35 +0200 28c8d3e55824 f3c974521ba0
line wrap: on
line source
\documentclass[a0paper, portrait]{tikzposter}

\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\usepackage{amsmath,amssymb,amsthm}
\usepackage[sc]{mathpazo}
\usepackage[all,pdf]{xy}
\usepackage[style=alphabetic]{biblatex}

% Thms. and Defns.
\newtheorem*{definition}{Definition}
\newtheorem*{thm}{Theorem}
\newtheorem*{prop}{Proposition}
\newtheorem*{lem}{Lemma}
\newtheorem*{cor}{Corollary}

\addbibresource{bib/mrzv13.bib}
\addbibresource{bib/bubenik14-02.bib}
\addbibresource{bib/bubenik14-01.bib}
\addbibresource{bib/chazal09.bib}
\addbibresource{bib/deSilva16.bib}

\usetheme{Default}
\usebackgroundstyle{Empty}
\usetitlestyle{Empty}

\title{Generic 1D-Interleavings}
\institute{Rheinische Friedrich-Wilhelms-Universität Bonn}
\author{Benedikt Fluhr}

\begin{document}
\input{macros.tex}
\SelectTips{cm}{12}
\maketitle
\begin{columns}
\column{0.5}
\block{Introduction}{
Suppose $$f \colon X \rightarrow \R$$ and $$g \colon Y \rightarrow \R$$
are continuous functions.
Then we may ask the following two questions:
\begin{itemize}
\item Is there a homeomorphism $$\varphi \colon X \rightarrow Y$$
such that
$\xymatrix@+10pt{ X \ar@/^/[rr]^{\varphi} \ar[dr]_{f} & & Y \ar[dl]^{g} \\ & \R }$
commutes?
(In the following we call $$\varphi$$ and any other continuous map
that fits into the above diagram a
\emph{homomorphism} from $$f$$ to $$g$$.
This augments the class of real-valued continuous functions
with the structure of a category,
the \emph{category of $$\R$$-spaces} for short.)
\item Is there a homeomorphism $$\varphi \colon X \rightarrow Y$$
and a real number $$r$$ such that
$\xymatrix@+15pt@C+30pt{ X \ar[r]^{\varphi} \ar[d]_f & Y \ar[d]^g \\ \R \ar[r]_{(r + \_)} & \R }$
commutes? (In other words
$$r + f(p) = g(\varphi(p))$$ for all $$p \in X$$.)
\end{itemize}
If the answer to either of the above questions is no,
we may still ask a weaker question.
Instead of commutativity of the above diagrams,
we only ask for commutivity up to $$\varepsilon$$ for some
$$\varepsilon \geq 0$$.
For $$\varepsilon \geq 0$$ we have the two questions:
\begin{itemize}
\item Is there a homeomorphism $$\varphi \colon X \rightarrow Y$$
such that for all $$p \in X$$ the estimates
$$-\varepsilon \leq f(p) - g(\varphi(p)) \leq \varepsilon$$
hold?
\item Is there a homeomorphism $$\varphi \colon X \rightarrow Y$$
and a real number $$r$$ such that for all $$p \in X$$ the estimates
$$-\varepsilon \leq r + f(p) - g(\varphi(p)) \leq \varepsilon$$
hold?
\end{itemize}
Now both these questions depend on the parameter $$\varepsilon \geq 0$$
and for either question we may ask how large does
$$\varepsilon$$ need to be in order for the answer to be \emph{yes}.
\begin{definition}
Let $$M(f, g)$$ be the infimum of all $$\varepsilon \geq 0$$
such that the answer to the first question is affirmative.
We name this \emph{the absolute distance of $$f$$ and $$g$$}.

And let $$\mu(f, g)$$ be the infimum of all $$\varepsilon \geq 0$$
such that the answer to the second question is affirmative.
We name this \emph{the relative distance of $$f$$ and $$g$$}.
\end{definition}
In the very first question we ask
whether $$f$$ and $$g$$ are isomorphic in the
category of $$\R$$-spaces.
Thus we may apply a functor $$F$$ from the category of
$$\R$$-spaces to a category
in which it is easier to decide whether two objects are isomorphic or not.
If $$F(f)$$ and $$F(g)$$ are isomorphic,
then we still don't know.
But if $$F(f)$$ and $$F(g)$$ are not isomorphic,
then we know the answer is \emph{no}.
Similarly we may never learn the absolute or relative distance
of $$f$$ and $$g$$
but we may try to find lower bounds to either value.
To this end functors from the category of $$\R$$-spaces
may be useful, but this concept alone doesn't solve our problem.
In the following we describe a framework for \emph{enhancing} functors
from the category of $$\R$$-spaces to obtain
lower bounds for $$M(f, g)$$ and $$\mu(f, g)$$.
On several aspects this borrows from \cite{bubenik2014-02}.

The work presented here is supported by the DFG-project
\emph{DFG \hbox{(KL 655/19)} \hbox{(D-A-CH)}}
and a part of my master's thesis
supervised by Professor Rolf Klein.
His advice has always been very useful and relevant to my work.
}
\block{Monoidal Posets for 1D-Interleavings}{
\begin{definition}
Let
$$D := \set{(a, b)}{[-\infty, \infty) \times (-\infty, \infty]} {a \leq b}$$
then $$D$$ is a monoid by component-wise addition.
Moreover we set $$\mathbf{o} := (0, 0)$$ and
we define a partial order $$\preceq$$ on $$D$$ by
$(x, y) \preceq (x', y') \quad \text{if and only if} \quad x \geq x' ~~ \text{and} ~~ y \leq y' .$
\end{definition}
A set augmented with a partial ordering and a monoid structure
like $$D$$, we call a \emph{monoidal poset}.
Moreover $$D \times D$$ is a monoidal poset with the product ordering
and component-wise addition.
With some abuse of notation we write
$$(a, b; c, d)$$ for points $$((a, b), (c, d)) \in D \times D$$.
Now we define three monoidal sub-posets of $$D \times D$$.
\begin{definition}
We set
\begin{itemize}
\item $$\mathcal{D} := \set{(a, b; c, d)}{D \times D} {a + c \leq 0 \leq b + d}$$,
\item $$\triangledown := \set{(a, b; c, d)}{\mathcal{D}} {c + b = 0 = a + d}$$, and
\item $$\blacktriangledown := \set{(a, b; c, d)}{\triangledown} {a + b = 0}$$.
\end{itemize}
\end{definition}
Both the inclusion of $$\triangledown$$ into $$\mathcal{D}$$
and the inclusion of $$\blacktriangledown$$ into $$\triangledown$$
each have a lower adjoint in the sense of monotone Galois connections.
\begin{definition}
Let $$\delta \colon \mathcal{D} \rightarrow \triangledown$$
be the lower adjoint of $$\triangledown \subset \mathcal{D}$$
and let
$$\gamma \colon \triangledown \rightarrow \blacktriangledown$$
be the lower adjoint of $$\blacktriangledown \subset \triangledown$$.
\end{definition}
We note that both $$\delta$$ and $$\gamma$$ are sub-linear,
i.e. oplax monoidal as functors.
We use these maps to describe two weightings on $$\mathcal{D}$$.
\begin{definition}
We set
$$\epsilon \colon \triangledown \rightarrow [0, \infty], (a, b; c, d) \mapsto \frac{1}{2} (b + d)$$.
\end{definition}
We note that $$\epsilon$$ is a (strict) homomorphism of monoidal posets.
Moreover the restriction $$\epsilon |_{\blacktriangledown}$$ is an
isomorphism.
The compositions
$$\epsilon \circ \gamma \circ \delta$$ and $$\epsilon \circ \delta$$
yield two different weightings on $$\mathcal{D}$$.
It turns out
$$(\epsilon \circ \gamma \circ \delta)((a, b; c, d)) = \max \{-a, b, -c, d\}$$
and
$$(\epsilon \circ \delta)((a, b; c, d)) = \frac{1}{2} (\max \{-c, b\} + \max \{-a, d\})$$
for all $$(a, b; c, d) \in \mathcal{D}$$.
}
\column{0.5}
\block{Interleavings in $$D$$-modules}{
\begin{definition}[$$D$$-modules]
A \emph{$$D$$-module} is a category $$\mathcal{C}$$
with a strict monoidal functor $$\mathcal{S}$$ from $$D$$
to the category of endofunctors on $$\mathcal{C}$$.
We refer to $$\mathcal{S}$$ as the
\emph{smoothing functor of $$\mathcal{C}$$}.
\end{definition}
Now let $$\mathcal{C}$$ be a $$D$$-module
with smoothing functor $$\mathcal{S}$$.
For $$a \leq 0$$, $$b \geq 0$$, and an object $$A$$ in $$\mathcal{C}$$
we get two things,
the image $$\mathcal{S}((a, b))(A)$$ of $$A$$
under the endofunctor $$\mathcal{S}((a, b))$$
and a natural homomorphism from $$A$$ to
$$\mathcal{S}((a, b))(A)$$ induced by
$$\mathbf{o} \preceq (a, b)$$.
With some abuse of notation we denote this homomorphism
by $$\mathcal{S}((a, b))_A$$.
Now let $$A$$ and $$B$$ be objects in $$\mathcal{C}$$.
\begin{definition}[Interleavings]
For $$(\mathbf{a}, \mathbf{b}) \in \mathcal{D}$$ an
\emph{$$(\mathbf{a}, \mathbf{b})$$-interleaving of $$A$$ and $$B$$}
is a pair of homomorphisms
$$\varphi \colon A \rightarrow \mathcal{S}(\mathbf{a})(B)$$ and
$$\psi \colon B \rightarrow \mathcal{S}(\mathbf{b})(A)$$
such that
$\xymatrix@+15pt{ A \ar@/^/[rr]^{\mathcal{S}(\mathbf{a} + \mathbf{b})_A \qquad} \ar[dr]|-{\varphi} & & \mathcal{S}(\mathbf{a} + \mathbf{b})(A) \\ & \mathcal{S}(\mathbf{a})(B) \ar[ru]|-{\mathcal{S}(\mathbf{a})(\psi)} } \quad \text{and} \quad \xymatrix@+15pt{ B \ar@/^/[rr]^{\mathcal{S}(\mathbf{a} + \mathbf{b})_B \qquad} \ar[dr]|-{\psi} & & \mathcal{S}(\mathbf{a} + \mathbf{b})(B) \\ & \mathcal{S}(\mathbf{b})(A) \ar[ru]|-{\mathcal{S}(\mathbf{b})(\varphi)} }$
commute.

We say \emph{$$A$$ and $$B$$ are $$(\mathbf{a}, \mathbf{b})$$-interleaved}
if there is an $$(\mathbf{a}, \mathbf{b})$$-interleaving
of $$A$$ and $$B$$.
\end{definition}
Now we use the weightings on $$\mathcal{D}$$ described on the previous
card to describe two notions of an interleaving distance.
\begin{definition}
Let $$\mathcal{I}$$ be the set of all
$$(\mathbf{a}, \mathbf{b}) \in \mathcal{D}$$ such that there is
an $$(\mathbf{a}, \mathbf{b})$$-interleaving of $$A$$ and $$B$$.
Then we set
$M_{\mathcal{S}}(A, B) := \inf (\epsilon \circ \gamma \circ \delta)(\mathcal{I}) \quad \text{and} \quad \mu_{\mathcal{S}}(A, B) := \inf (\epsilon \circ \delta)(\mathcal{I}).$
We name $$M(A, B)$$ the
\emph{absolute interleaving distance of $$A$$ and $$B$$}
and $$\mu(A, B)$$ the
\emph{relative interleaving distance}.
\end{definition}
Now let $$\mathcal{C}'$$ be another $$D$$-module with smoothing
functor $$\mathcal{S}'$$.
\begin{definition}
A $$1$$-homomorphism of $$D$$-modules
from $$\mathcal{C}$$ to $$\mathcal{C}'$$
is a functor from $$\mathcal{C}$$ to $$\mathcal{C}'$$ such that
$G \circ \mathcal{S} (\mathbf{a}) = \mathcal{S}' (\mathbf{a}) \circ G \quad \text{and} \quad G \circ \mathcal{S} (\mathbf{a} \preceq \mathbf{b}) = \mathcal{S}' (\mathbf{a} \preceq \mathbf{b}) \circ G$
for all $$\mathbf{a}, \mathbf{b} \in D$$ with
$$\mathbf{a} \preceq \mathbf{b}$$.
\end{definition}
\begin{thm}
Let $$G$$ be a $$1$$-homomorphism from
$$\mathcal{C}$$ to $$\mathcal{C}'$$,
then
$M_{\mathcal{S}'}(G(A), G(B)) \leq M_{\mathcal{S}}(A, B) \quad \text{and} \quad \mu_{\mathcal{S}'}(G(A), G(B)) \leq \mu_{\mathcal{S}}(A, B) .$
\end{thm}
}
\block{Persistence-enhanced Functors}{
\begin{definition}
Let $$f \colon X \rightarrow \R$$ and
$$g \colon X \rightarrow \R$$ be continuous functions
and let $$(a, b), (c, d) \in D$$.
Then a \emph{homomorphism from $$(f, (a, b))$$ to $$(g, (c, d))$$}
is a continuous map $$\varphi \colon X \rightarrow Y$$ such that
$$c - a \leq f(p) - g(\varphi(p)) \leq d - b$$
for all $$p \in X$$.

This defines a category which we denote by $$\mathcal{F}$$.
\end{definition}
Next we define a smoothing functor for $$\mathcal{F}$$.
\begin{definition}
Let $$f \colon X \rightarrow \R$$
be a continuous function and let
$$\mathbf{a}, \mathbf{b}, \mathbf{c} \in D$$
with
$$\mathbf{b} \preceq \mathbf{c}$$.
Then we set
$$\mathcal{T}(\mathbf{b})((f, \mathbf{a})) := (f, \mathbf{a} + \mathbf{b})$$
and
$$\mathcal{T}(\mathbf{b} \preceq \mathbf{c})_{(f, \mathbf{a})} := \id_X$$.
\end{definition}
\begin{lem}
For two $$\R$$-spaces $$f$$ and $$g$$ we have
$M(f, g) = M_{\mathcal{T}}((f, \mathbf{o}), (g, \mathbf{o})) \quad \text{and} \quad \mu(f, g) = \mu_{\mathcal{T}}((f, \mathbf{o}), (g, \mathbf{o})) .$
\end{lem}
Now let $$F$$ be a functor from the category of $$\R$$-spaces
to a category $$\mathcal{C}$$.
\begin{definition}
A \emph{persistence-enhancement of $$F$$}
is the structure of a $$D$$-module on $$\mathcal{C}$$
together with a $$1$$-homomorphism $$\tilde{F}$$ from
$$\mathcal{F}$$ to $$\mathcal{C}$$ such that
$$\tilde{F}((\_, \mathbf{o})) = F$$.
\end{definition}
The previous lemma and the theorem from the previous card have
the following
\begin{cor}
If there is a persistence-enhancement of $$F$$
with smoothing functor $$\mathcal{S}$$,
then we have
$M_{\mathcal{S}}(F(f), F(g)) \leq M(f, g) \quad \text{and} \quad \mu_{\mathcal{S}}(F(f), F(g)) \leq \mu(f, g)$
for all $$\R$$-spaces $$f$$ and $$g$$.
\end{cor}
Finally we note that the \emph{interleaving distances}
provided in \cite{chazal2009}, \cite{morozov2013}, \cite{bubenik2014-01},
and \cite{deSilva2016}
can each be realized as the
absolute interleaving distance of a corresponding persistence-enhanced
functor.
}
\block{References}{\printbibliography[heading=none]}
\end{columns}
\end{document}