view poster.tex @ 15:1cb388196827

Change of layout
author Benedikt Fluhr <http://bfluhr.com>
date Mon, 17 Apr 2017 20:37:35 +0200
parents 28c8d3e55824
children 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}