Wavelets auf einem Graphen

6 files changed, 292 insertions, 23 deletions

diff --git a/buch/chapters/70-graphen/beschreibung.tex b/buch/chapters/70-graphen/beschreibung.tex
index 25cfcc0..a0f46da 100644
--- a/buch/chapters/70-graphen/beschreibung.tex
+++ b/buch/chapters/70-graphen/beschreibung.tex
@@ -401,7 +401,7 @@ Sie hat für $i\ne j$ die Einträge
 \\
 &=\text{Anzahl der Kanten, die $i$ mit $j$ verbinden}
 \\
-&=a_{ij}
+&=a_{ij}.
 \end{align*}
 Die Adjazenzmatrix eines Graphen lässt sich also aus der
 Inzidenzmatrix berechnen.
diff --git a/buch/chapters/70-graphen/images/Makefile b/buch/chapters/70-graphen/images/Makefile
index d34247b..5db54c8 100644
--- a/buch/chapters/70-graphen/images/Makefile
+++ b/buch/chapters/70-graphen/images/Makefile
@@ -4,7 +4,7 @@
 # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
 #
 all:	peterson.pdf adjazenzu.pdf adjazenzd.pdf kreis.pdf fundamental.pdf \
-	petersonchrind.pdf nine.pdf
+	petersonchrind.pdf nine.pdf gh.pdf
 
 peterson.pdf:	peterson.tex
 	pdflatex peterson.tex
@@ -26,3 +26,6 @@ fundamental.pdf:	fundamental.tex
 nine.pdf:	nine.tex
 	pdflatex nine.tex
 
+gh.pdf:	gh.tex
+	pdflatex gh.tex
+
diff --git a/buch/chapters/70-graphen/images/gh.pdf b/buch/chapters/70-graphen/images/gh.pdf
new file mode 100644
index 0000000..c6e48d7
--- /dev/null
+++ b/buch/chapters/70-graphen/images/gh.pdf
diff --git a/buch/chapters/70-graphen/images/gh.tex b/buch/chapters/70-graphen/images/gh.tex
new file mode 100644
index 0000000..fcceb5f
--- /dev/null
+++ b/buch/chapters/70-graphen/images/gh.tex
@@ -0,0 +1,55 @@
+%
+% gh.tex -- Lokalsierungsfunktionen für Wavelets auf einem Graphen
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\documentclass[tikz]{standalone}
+\usepackage{amsmath}
+\usepackage{times}
+\usepackage{txfonts}
+\usepackage{pgfplots}
+\usepackage{csvsimple}
+\usetikzlibrary{arrows,intersections,math}
+\begin{document}
+\def\skala{1}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+\definecolor{darkgreen}{rgb}{0,0.6,0}
+
+\def\kurve#1#2{
+	\draw[color=#2,line width=1.4pt]
+		plot[domain=0:6.3,samples=400]
+			({\x},{7*\x*exp(-(\x/#1)*(\x/#1))/#1});
+}
+
+\begin{scope}
+
+\draw[->] (-0.1,0) -- (6.6,0) coordinate[label={$\lambda$}];
+
+\kurve{1}{red}
+\foreach \k in {0,...,4}{
+	\pgfmathparse{0.30*exp(ln(2)*\k)}
+	\xdef\l{\pgfmathresult}
+	\kurve{\l}{blue}
+}
+
+\node[color=red] at ({0.7*1},3) [above] {$g(\lambda)$};
+\node[color=blue] at ({0.7*0.3*16},3) [above] {$g_i(\lambda)$};
+
+\draw[->] (0,-0.1) -- (0,3.3);
+\end{scope}
+
+\begin{scope}[xshift=7cm]
+
+\draw[->] (-0.1,0) -- (6.6,0) coordinate[label={$\lambda$}];
+
+\draw[color=darkgreen,line width=1.4pt]
+	plot[domain=0:6.3,samples=100] 
+		({\x},{3*exp(-(\x/0.5)*(\x/0.5)});
+
+\draw[->] (0,-0.1) -- (0,3.3) coordinate[label={right:$\color{darkgreen}h(\lambda)$}];
+
+\end{scope}
+
+\end{tikzpicture}
+\end{document}
+
diff --git a/buch/chapters/70-graphen/spektral.tex b/buch/chapters/70-graphen/spektral.tex
index 571b7e1..5fb3056 100644
--- a/buch/chapters/70-graphen/spektral.tex
+++ b/buch/chapters/70-graphen/spektral.tex
@@ -56,8 +56,10 @@ Eine minimale Färbung des Graphen mit $\operatorname{chr}G$ Farben
 teilt die Knoten in $\operatorname{chr}G$ Mengen $V_f$ von Knoten mit
 gleicher Farbe $f$ ein.
 Da diese Mengen einfarbig sind, sind sie unabhängig, enthalten also
-höchstens so viele Knoten, wie die Unabhängigkeitszahl erlaubt.
-Die Gesamtzahl der Knoten ist also
+höchstens so viele Knoten, wie die Unabhängigkeitszahl erlaubt,
+also $|V_f|\le \operatorname{ind}G$.
+Da die Menge aller Knoten die Vereinigung der Mengen $V_f$ ist,
+ist die Gesamtzahl der Knoten 
 \begin{align*}
 V
 &=
@@ -66,15 +68,15 @@ V
 n
 &=
 \sum_{\text{$f$ eine Farbe}} |V_f| 
-\le
-\sum_{\text{$f$ eine Farbe}} \operatorname{ind}G
-=
-(\text{Anzahl Farben})\cdot \operatorname{ind}G
 \\
 &
 &&&
-&=
-\operatorname{chr}G \cdot \operatorname{ind}G
+&\le
+\sum_{\text{$f$ eine Farbe}} \operatorname{ind}G
+=
+(\text{Anzahl Farben})\cdot \operatorname{ind}G
+=
+\operatorname{chr}G \cdot \operatorname{ind}G.
 \end{align*}
 Damit ist $n\le \operatorname{chr}G\cdot\operatorname{ind}G$ gezeigt.
 \qedhere
@@ -117,7 +119,7 @@ Nach Definition ist Unabhängigkeitszahl ein Mass für die Grösse einer
 unabhängigen Menge von Punkten.
 Der Beweis von Satz~\ref{buch:satz:chrind} zeigt, dass man sich die
 chromatische Zahl als ein Mass dafür, wieviele solche anabhängige 
-Mengen in einem Grapehn untergebracht werden können.
+Mengen in einem Graphen untergebracht werden können.
 
 %
 % Chromatische Zahl und maximaler Grad
@@ -131,7 +133,7 @@ Einfärbung des ganzen Graphen reichen.
 Genau dies garantiert jedoch der folgende Satz.
 
 \begin{definition}
-Der {\em maximale Grad} 
+Der maximale Grad
 \(
 \max_{v\in V} \deg(v)
 \)
@@ -455,7 +457,8 @@ Satz~\ref{buch:graphen:satz:chrmaxgrad}
 die Schranke 
 $\operatorname{chr}G\le 4+1=5$
 für die chromatische Zahl.
-Der Satz von Wilf ist also eine wesentliche Verbesserung.
+Der Satz von Wilf ist also eine wesentliche Verbesserung, er liefert in
+diesem Fall den exakten Wert der chromatischen Zahl.
 \end{beispiel}
 
 
diff --git a/buch/chapters/70-graphen/wavelets.tex b/buch/chapters/70-graphen/wavelets.tex
index 9c88c08..ae065bc 100644
--- a/buch/chapters/70-graphen/wavelets.tex
+++ b/buch/chapters/70-graphen/wavelets.tex
@@ -103,22 +103,230 @@ 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 und Frequenzspektrum}
-Eine Wavelet-Basis der Funktionen auf $\mathbb{R}$ zerlegt
+\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}
+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$ zu finden
+derart, dass man sich die $\chi_j$ in einem gewissen Sinn als aus
+$\chi_0$ durch Dilatation entstanden vorstellen kann.
 
-\subsection{Frequenzspektrum
-\label{buch:subsection:frequenzspektrum}}
-Die Fundamentallösung der Wärmeleitunsgleichung haben ein Spektrum, welches
-wie $e^{-k^2}$ gegen $0$ geht.
+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 zeichnet 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, Eigenbasis der Laplace-Matrix 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 Fundamentallösung entsteht dadurch, dass die hohen Frequenzen
-schneller dämpft als die tiefen Frequenzen.
+Die Matrix $g(I)$ bildet entfernt aus einer Funktion die ganz hohen und 
+die ganz tiefen Frequenz, 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(I)$ kann mit Hilfe der Spektraltheorie berechnet werden,
+was im vorliegenden Fall naheliegend ist, weil ja die Eigenvektoren von
+der Laplace-Matrix bereits bekannt sind.
+Die Matrix $\chi^t$ bildet die Standardbasisvektoren in die
+Eigenbasis-Vektoren ab, also in eine Zerlegung im Frequenzraum ab,
+$\chi$ vermittelt die Umkehrabbildung.
+Mit der Spektraltheorie findet man für die Abbildung $g(I)$ die Matrix
+\begin{equation}
+g(I)
+=
+\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}
 
-\subsection{Wavelet-Basen
-\label{buch:subsection:}}
+\subsubsection{Dilatation}
+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(I)$
+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(I)
+=
+g_i(I)
+=
+\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(I)$ 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(I)$ 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(I)$ bildet daher den konstanten Vektor nicht auf $0$ ab,
+sondern lokalisiert ihn im Ortsraum.
+Wir erhalten daher in den Spalten von $h(I)$ Vektoren, die um die
+einzelnen Knoten lokalisiert sind.
+
+\subsubsection{Rekonstruktion}
+Die Operatoren $h(I)$ und $g_i(I)$ erzeugen 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(I) + \sum_{i}g_i(I)=I
+\]
+gelten würde.
+Nach der Spektraltheorie gilt das nur, wenn für alle Eigenwerte
+$\lambda_k$, $k=1,\dots,n$
+\[
+h(\lambda_k) + \sum_ig(a_i\lambda_k)=1
+\]
+gilt.
+Für beleibige Funktionen $g$ und $h$ kann man nicht davon ausgehen,
+aber man kann erwarten.
+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\;|\; 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 Spalten Vektoren von $h(I)$ und $g_i(I)$
+bilden daher ein Frame.
+Die Frame-Konstanten kann man unmittelbar ausrechnen.
+Der mittlere Term von \eqref{buch:graphen:eqn:frame} ist 
+\[
+\|h(I) v\|^2
++
+\sum_{i} \|g_i(I)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{align*}
+A&=\min_{k} f(\lambda_k)
+&
+&\text{und}&
+B&=\max_{k} f(\lambda_k).
+\end{align*}
+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.