path: root/buch/chapters/70-graphen/wavelets.tex

%
% wavelets.tex -- Wavelets auf Graphen
%
% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
%
\section{Wavelets auf Graphen
\label{buch:section:wavelets-auf-graphen}}
\rhead{Wavelets auf Graphen}
In Abschnitt~\ref{buch:subsection:standardbasis-und-eigenbasis} wurde
gezeigt dass die Standardbasis den Zusammenhang zwischen den einzelnen
Teilen des Graphen völlig ignoriert, während die Eigenbasis Wellen
beschreibt, die mit vergleichbarer Amplitude sich über den ganzen
Graphen erstrecken.
Die Eigenbasis unterdrückt also die ``Individualität'' der einzelnen
Knoten fast vollständig.

Wenn man einen Standardbasisvektor in einem Knoten $i$
als Anfangstemperaturverteilung verwendet, erwartet man eine Lösung,
die für kleine Zeiten $t$ die Energie immer in der Nähe des Knotens $i$
konzentriert hat.
Es werden daher mit der Zeit immer stärkere benachbarte Standardbasisvektoren
in der Lösung auftreten.
Auch die Eigenbasis hilft nicht, dieses Lösungsverhalten aufzuzeigen:
sie sind im Definitionsgebiet stark delokalisiert und daher die allmählich
abnehmende Lokalisierung der Lösung nicht wiedergeben.

\subsection{Vergleich mit der Wärmeleitung auf $\mathbb{R}$}
Ein ähnliches Phänomen findet man bei der Wärmeausbreitung gemäss
der partiellen Differentialgleichung
\[
\frac{\partial T}{\partial t} = -\kappa \frac{\partial^2 T}{\partial x^2}.
\]
Die von Fourier erfundene Methode, die Fourier-Theorie, verwendet die
Funktionen $e^{ik x}$, die Eigenvektoren der zweiten Ableitung
$\partial^2/\partial x^2$ sind.
Diese haben das gleiche Problem: Der Betrag von $e^{ikx}$ ist $1$, die
Entfernung von einem Punkt spielt überhaupt keine Rolle.
Die Funktion
\[
F(x,t)
=
\frac{1}{\sqrt{4\pi\kappa t}}e^{-x^2/4\kappa t}
\]
ist eine Lösung der Wärmeleitungsgleichung mit einem Maximum an
der Stelle $0$.
Sie heisst die Fundamentallösung der Wärmeleitungsgleichung.
Durch Überlagerung von Translaten in eine Funktion
\begin{equation}
f(x,t)
=
\int_{-\infty}^\infty f(\xi) F(x-\xi,t)\,d\xi
\label{buch:graphen:eqn:fundamentalueberlagerung}
\end{equation}
kann man die allgemeine Lösung aus Fundamentallösungen zusammensetzen.
Die Fundamentallösungen $f(x-\xi,t)$ sind für kleine Zeiten immer noch
deutlich in einer Umgebung von $\xi$ konzentriert.

\begin{figure}
\centering
\includegraphics{chapters/70-graphen/images/fundamental.pdf}
\caption{Vergleich der verschiedenen Funktionenfamilien, mit denen
Lösungenfunktionen durch Linearkombination erzeugt werden können.
In der Standarbasis (links) ist es am einfachsten, die Funktionswerte
abzulesen, in der Eigenbasis (Mitte) kann die zeitliche Entwicklung
besonders leicht berechnet werden.
Dazwischen liegen die Fundamentallösungen (rechts), die eine einigermassen
übersichtliche Zeitentwicklung haben, die Berechnung der Temperatur an 
einer Stelle $x$ zur Zeit $t$ ist aber erst durch das Integral
\eqref{buch:graphen:eqn:fundamentalueberlagerung} gegeben.
\label{buch:graphen:fig:fundamental}}
\end{figure}

\subsection{Fundamentallösungen auf einem Graphen}
Die Wärmeleitungsgleichung auf einem Graphen kann für einen
Standardbasisvektor mit Hilfe der
Lösungsformel~\eqref{buch:graphen:eqn:eigloesung}
gefunden werden.
Aus physikalischen Gründen ist aber offensichtlich, dass die
Wärmeenergie der Fundamentallösungen $F_i(t)$ für kurze Zeiten $t$
in der Nähe des Knotens $i$ konzentriert ist.
Dies ist aber aus der Fourier-Entwicklung
\begin{equation}
F_i(t)
=
\sum_{j=1}^n \langle \chi_j,e_i\rangle e^{-\kappa \lambda_i t} \chi_j
=
\sum_{j=1}^n \overline{f}_{ji} e^{-\kappa \lambda_i t},
\label{buch:graphen:eqn:fundamentalgraph}
\end{equation}
nicht unmittelbar erkennbar.

Man kann aber aus~\eqref{buch:graphen:eqn:fundamentalgraph}
wenigstens ablesen,
dass für zunehmende Zeit die hohen Frequenzen sehr schnell gedämpft
werden.
Die hohen Frequenzen erzeugen also den scharfen Peak für Zeiten nahe
beim Knoten $i$, die kleineren $\lambda_i$ beschreiben die Ausbreitung
über grössere Distanzen.
Die Fundamentallösung interpoliert also in einem gewissen Sinne zwischen
den Extremen der Standardbasis und der Eigenbasis.
Die ``Interpolation'' geht von der Differentialgleichung aus,
sie ist nicht einfach nur ein Filter, der die verschiedenen Frequenzen
auf die gleiche Art bearbeitet.

Gesucht ist eine Methode, eine Familie von Vektoren zu finden,
aus der sich alle Vektoren linear kombinieren lassen, in der aber
auch auf die für die Anwendung interessante Längenskala angepasste
Funktionen gefunden werden können.

\subsection{Wavelets auf einem Graphen}
Die Fourier-Theorie analysiert Funktionen nach Frequenzen, wobei die 
zeitliche Position von interessanten Stellen der Funktion in der Phase
der einzelnen Komponenten verschwindet.
Die Lokalisierung geht also für viele praktische Zwecke verloren.
Umgekehrt haben einzelne Ereignisse wie eine $\delta$-Funktion keine
charakteristische Frequenz, sie sind daher im Frequenzraum überhaupt 
nicht lokalisierbar.
Die Darstellung im Frequenzraum und in der Zeit sind also extreme
Darstellungen, entweder Frequenzlokalisierung oder zeitliche Lokalisierung
ermöglichen, sich aber gegenseitig ausschliessen.

\subsubsection{Dilatation im Frequenzraum, spektrale Dilatation}
Eine Wavelet-Basis für die $L^2$-Funktionen auf $\mathbb{R}$ erlaubt
eine Funktion auf $\mathbb{R}$ auf eine Art zu analysieren, die eine
ungenaue zeitliche Lokalisierung bei entsprechend ungenauer
Frequenzbestimmung ermöglicht.
Ausserdem entstehen die Wavelet-Funktionen aus einer einzigen Funktion
$\psi(t)$ durch Translation um $b$ und Dilatation mit dem Faktor $a$:
\[
\psi_{a,b}(t)
=
\frac{1}{\sqrt{|a|}} \psi\biggl(\frac{t-b}a\biggr)
=
T_bD_a\psi(t)
\]
in der Notation von \cite{buch:mathsem-wavelets}.
Auf einem Graphen ist so eine Konstruktion grundsätzlich nicht möglich,
da es darauf weder eine Translations- noch eine Streckungsoperation gibt.

In der Theorie der diskreten Wavelet-Transformation ist es üblich, sich
auf Zweierpotenzen als Streckungsfaktoren zu beschränken.
Ein Gitter wird dadurch auf sich selbst abgebildet, aber auf einem
Graphen gibt es keine Rechtfertigung für diese spezielle Wahl von
Streckungsfaktoren mehr.
Es stellt sich daher die Frage, ob man für eine beliebige Menge
\(
T= \{ t_1,t_2,\dots\}
\)
von Streckungsfaktoren eine Familie von Funktionen $\chi_j$ finden
derart, dass man sich die $\chi_j$ in einem gewissen Sinn als aus
$\chi_0$ durch Dilatation entstanden vorstellen kann.

Die Dilatation kann natürlich nicht von einer echten
Dilatation im Ortsraum herstammen, aber man kann wenigstens versuchen, die
Dilatation im Frequenzraum nachzubilden.
Für Funktionen in $L^2(\mathbb{R})$ entspricht die Dilatation mit dem
Faktor $a$ im Ortsraum der Dilatation mit dem Faktor $1/a$ im Frequenzraum:
\[
\widehat{D_af}(\omega) = D_{1/a}\hat{f}(\omega).
\]
\cite[Satz~3.14]{buch:mathsem-wavelets}.
Es bleibt aber das Problem, dass sich auch die Skalierung im Frequenzraum
nicht durchführen lässt, da auch das Frequenzspektrum des Graphen nur eine
Menge von reellen Zahlen ohne innere algebraische Struktur ist.

\subsubsection{Mutterwavelets}
\begin{figure}
\centering
\includegraphics{chapters/70-graphen/images/gh.pdf}
\caption{Lokalisierungsfunktion $g(\lambda)$ für die Dilatation (links).
Die dilatierten Funktionen $g_i=\tilde{D}_{1/a_i}g$ lokalisieren
die Frequenzen jeweils um die Frequenzen $a_i$ im Frequenzraum.
Der Konstante Vektor ist vollständig delokalisiert, die Funktion $h$
in der rechten Abbildung entfernt die hohen Frequenzen und liefert Funktionen,
die in der Umgebung eines Knotens wie die konstante Funktion aussehen.
\label{buch:graphs:fig:lokalisierung}}
\end{figure}
Das Mutter-Wavelet einer Wavelet-Analyse definiert, in welchem Mass
sich Funktionen im Orts- und im Frequenzraum lokalisieren lassen.
Die Standardbasis der Funktionen auf einem Graphen repräsentieren die
perfekte örtliche Lokalisierung, die Eigenbasis der Laplace-Matrix
$L$ repräsentiert die perfekte Lokalisierung im Frequenzraum.
Sei $g(\lambda)\ge 0$ eine Funktion im Frequenzraum, die für  $\lambda\to0$ und
$\lambda\to\infty$ rasch abfällt mit einem Maximum irgendwo dazwischen
(Abbildung~\ref{buch:graphs:fig:lokalisierung}).
Sie kann als eine Lokalisierungsfunktion im Frequenzraum betrachtet werden.

Die Matrix $g(L)$ entfernt die ganz hohen und die ganz tiefen Frequenz
aus einer Funktion, lokalisiert also die Funktionen im Frequenzraum.
Die Standardbasisvektoren werden dabei zu Funktionen, die nicht mehr nur
auf einem Knoten von $0$ verschieden sind, aber immer noch einigermassen
auf dem Graphen lokalisiert sind.
Natürlich sind vor allem die Werte auf den Eigenwerten
$\lambda_0 < \lambda_1\le \dots\le \lambda_n$ der Laplace-Matrix
von Interesse.

Die Matrix $g(L)$ kann mit Hilfe der Spektraltheorie
von Abschnitt~\ref{buch:section:spektraltheorie}
berechnet werden,
was im vorliegenden Fall naheliegend ist, weil ja die Eigenvektoren 
der Laplace-Matrix bereits bekannt sind.
Die Matrix $\chi^t$ bildet die Standardbasisvektoren in die
Eigenbasis-Vektoren ab, also in eine Zerlegung im Frequenzraum,
$\chi$ vermittelt die Umkehrabbildung.
Mit der Spektraltheorie findet man für die Abbildung $g(L)$ die Matrix
\begin{equation}
g(L)
=
\chi
\begin{pmatrix}
g(\lambda_0)&0&\dots&0\\
0&g(\lambda_1)&\dots&0\\
\vdots&\vdots&\ddots&\vdots\\
0&0&\dots&g(\lambda_n)
\end{pmatrix}
\chi^t.
\label{buch:graphen:eqn:mutterwavelet}
\end{equation}

\subsubsection{Spektrale Dilatation der Mutterwavelets}
Die Dilatation um $a$ im Ortsraum wird zu einer Dilatation um $1/a$ im
Frequenzraum.
Statt also nach einer echten Dilatation der Spaltenvektoren in $g(L)$
zu suchen, kann man sich darauf verlegen, Funktionen zu finden, deren
Spektrum von einer Funktionen lokalisiert worden ist, die eine Dilatation
von $g$ ist.
Man wählt daher eine ansteigende Folge $A=(a_1,\dots)$ von Streckungsfaktoren
und betrachtet anstelle von $g$ die dilatierten Funktionen
$g_i=\tilde{D}_{1/a_i}g$.
Die zugehörigen Wavelet-Funktionen auf dem Graphen können wieder mit
der Formel~\eqref{buch:graphen:eqn:mutterwavelet} berechnet werden,
man erhält
\begin{equation}
\tilde{D}_{1/a_i}g(L)
=
g_i(L)
=
\chi
\begin{pmatrix}
g(a_i\lambda_0)&0&\dots&0\\
0&g(a_i\lambda_1)&\dots&0\\
\vdots&\vdots&\ddots&\vdots\\
0&0&\dots&g(a_i\lambda_n)
\end{pmatrix}
\chi^t .
\end{equation}
Die Spalten von $g_i(L)$ bilden wieder eine Menge von Funktionen, die
eine gemäss $g_i$ lokalisiertes Spektrum haben.

\subsubsection{Vater-Wavelet}
Wegen $g(0)=0$ wird die konstante Funktion, die Eigenvektor zum Eigenwert
$\lambda_0=0$ ist, von den Abbildungen $g_i(L)$ auf $0$ abgebildet.
Andererseits ist diese Funktion nicht lokalisiert, man möchte Sie also
für die Analyse nicht unbedingt verwenden.
Man wählt daher eine Funktion $h(\lambda)$ mit $h(0)=1$ so, dass
für $\lambda\to \infty$ der Wert $h(\lambda)$ genügend rasch gegen $0$
geht.
Die Matrix $h(L)$ bildet daher den konstanten Vektor nicht auf $0$ ab,
sondern lokalisiert ihn im Ortsraum.
Wir erhalten daher in den Spalten von $h(L)$ Vektoren, die um die
einzelnen Knoten lokalisiert sind.

\subsubsection{Rekonstruktion}
Die Operatoren $h(L)$ und $g_i(L)$ analysieren eine Funktion
nach den verschiedenen Frequenzen mit den Skalierungsfaktoren $a_i$,
aber die Rekonstruktion ist noch nicht klar.
Diese wäre einfacher, wenn die Operatoren zusammen die identische
Abbildung ergäben, wenn also
\[
h(L) + \sum_{i}g_i(L)=I
\]
gelten würde.
Nach der Spektraltheorie gilt das nur, wenn für alle Eigenwerte
$\lambda_k$, $k=1,\dots,n$
\begin{equation}
h(\lambda_k) + \sum_ig(a_i\lambda_k)=1
\label{buch:graphen:eqn:summegh}
\end{equation}
gilt.

Allerdings kann man im Allgemeinen nicht erwarten,
dass \ref{buch:graphen:eqn:summegh} für
beliebige Funktionen $g$ und $h$ gilt.
Da es aber nur auf die Werte auf den Eigenwerten ankommt,
muss nur sichergestellt sein, dass 
die linke Seite von \eqref{buch:graphen:eqn:summegh}
nicht verschwindet.
Dies garantiert, dass die Wavelet-Entwicklung umkehrbar ist.
Man muss daher zusätzlich verlangen, dass
\[
h(\lambda_k) + \sum_{i} g(a_i\lambda_k) > 0
\]
ist für alle Eigenwerte $\lambda_k$.

\subsubsection{Frame}
Die Menge von Vektoren, die in der vorangegangenen Konstruktion gefunden
wurden, ist zu gross, um eine Basis zu sein.
Vektoren lassen sich darin auf verschiedene Art darstellen.
Wir verlangen aber auch keine eindeutige Darstellung, nur eine 
Darstellung, in der wir die ``dominierenden'' Komponenten in jeder
Frequenzskala identifizieren können.

\begin{definition}
\label{buch:graphen:def:frame}
Ein Frame des Vektorraumes $\mathbb{R}^n$ ist eine Menge
$F=\{e_k \mid k=1,\dots,N\}$ von Vektoren mit der Eigenschaft
\begin{equation}
A\|v\|^2
\le
\sum_{k=1}^N  |\langle v,e_k\rangle|^2
\le
B\|v\|^2
\label{buch:graphen:eqn:frame}
\end{equation}
Die Zahlen $A$  und $B$ heissen die {\em Frame-Konstanten} des Frames.
\end{definition}

Die oben gefundenen Vektoren, die Spaltenvektoren von $h(L)$ und $g_i(L)$,
bilden daher ein Frame.
Die Frame-Konstanten kann man unmittelbar ausrechnen.
Der mittlere Term von \eqref{buch:graphen:eqn:frame} ist 
\[
\|h(L) v\|^2
+
\sum_{i} \|g_i(L)v\|^2,
\]
die durch die Funktion
\[
f(\lambda)
=
h(\lambda)^2 + \sum_i g_i(\lambda)^2
\]
abgeschätzt werden kann.
Die Frame-Konstanten sind daher
\[
\begin{aligned}
A&=\min_{k} f(\lambda_k)
&
&\text{und}&
B&=\max_{k} f(\lambda_k).
\end{aligned}
\]
Die Konstruktion hat also ein Frame für die Funktionen auf dem Graphen
etabliert, die viele Eigenschaften einer Multiskalenanalyse in diese
wesentlich weniger symmetrische Situation rettet.