## Home > hg > poster-acat01

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

Find changesets by keywords (author, files, the commit message), revision
number or hash, or revset expression.

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}