April 2012


This term I am teaching “Integraltransformation” and plan to put my lecture notes here. Since the lecture is German, the notes are also in German. Here is the first part:

1. Einleitung

Obwohl diese Vorlesung “Integraltransformationen” heißt, behandelt sie nicht nur solche, sondern auch anderen Arten von Transformationen. Konkret behandeln wir:

  • die {z}-Transformation,
  • die Laplace-Transformation,
  • die Fourier-Transformation,
  • Fourier-Reihen

und gegebenfalls noch

  • die Wavelet-Transformation,
  • die gefensterte Fourier-Transformation,
  • die Hilbert-Transformation,
  • die Zak-Transformation.

Die grundlegende Idee bei all diesen Transformationen ist es, einem mathematischen Objekt (zum Beispiel einer Funktion) ein anderes mathematisches Objekt zuzuordnen, welches die Information die das Objekt trägt in anderer Weise kodiert. Dieses neue Objekt kann es dann erlauben, bestimmte Eigenschaften einfacher abzulesen, oder es ist manchmal möglich, bestimmte Änderungen am Objekt in übersichtlicherer Weise darzustellen.

Obwohl alle genannten Transformationen mathematisch interessant und sehr hilfreich sind, haben sie ein Anwendungsfeld, welches nicht nur zur Motivation dient, sondern auch bei der Interpretation eine gute Hilfestellung bietet:

1.1. Signalverarbeitung

Unter einem Signal kann man verschiedenes verstehen – es geht auf jeden Fall um etwas, was Information kodiert und zur Übertragung von einer Stelle an eine andere geeignet ist. Dies kann zum Beispiel sein:

  • ein Schallsignal wie es vom MP3-Player durch das Kopfhörerkabel geleitet wird,
  • eine Folge von Bits wie sie durch das Netzwerkkabel vom Computer geleitet wird,
  • eine elektromagnetische Welle wie sie vom Handy zum Funkmast gesendet wird, oder auch
  • ein digitales Bild wie es auf der Speicherkarte eine Digitalkamera abgelegt wird.

Signale werden grob unterteilt:

  • Analoge Signale: Das “Signal” ist eine Funktion auf einem kontinuierlichen Definitionsbereich, hier ein kontinuierliches Zeitintervall. Beispiele sind das Schallsignal oder die elektromagnetische Welle.
  • Digitale Signale: Das “Signal” ist eine (endliche oder unendliche) Folge von Werten, wie die Bitfolge oder das Digitalbild.

Man könnte auch noch nach dem Wertebereich unterscheiden (ist er diskret, wie bei der Bitfolge und dem Bild, oder kontinuierlich, wie beim Schallsignal). In dieser Vorlesung wird diese Unterscheidung keine Rolle spielen – unsere Signale haben immer kontinuierliche Werte (meist reelle oder komplexe Zahlen).

Eine zentrale Frage der Signalverarbeitung ist es, wie aus analogen Signalen digitale Signale gewonnen werden und wie der umgekehrte Weg beschritten werden kann. Die Thematik läuft unter dem Namen “Abtasten” und “Interpolieren” (innerhalb der E-Technik auch AD- und DA-Konversion; Analog-Digital bzw. Digital-Analog). Weitere Aufgaben sind die Abwandlung/Bearbeitung von Signalen oder auch die Kompression.

Wir werden zwar keine Signalverarbeitung im eigentlichen Sinn behandeln, aber es wird im Folgenden hilfreich sein, sich der Intuition zu bedienen, dass es sich bei den auftretenden Funktionen und Folgen um kontinuierliche bzw.~diskrete Signale handelt.

1.2. Etwas Notation

Wir bezeichen mit {{\mathbb N}} die natürlichen Zahlen (inklusive Null), mit {{\mathbb Z}} die ganzen Zahlen, mit {{\mathbb R}} die reellen und mit {{\mathbb C}} die komplexen Zahlen.

Eine Funktion {f:{\mathbb R}\rightarrow{\mathbb C}} bezeichnen wir auch als komplexwertiges kontinuierliches Signal. Eine Abbildung {f:{\mathbb Z}\rightarrow{\mathbb R}} nennen wir auch reellwertiges diskretes Signal (auch {f:{\mathbb N}\rightarrow{\mathbb R}} wird so genannt). Analog sind natürlich reellwertige kontinuierliche Signale und komplexwertige diskrete Signale zu verstehen. Im Falle von diskreten Signalen benutzen wir auch die Schreibweise {f_n = f(n)} (wie bei Folgen üblich).

Mit {{\mathbb R}^n} bzw {{\mathbb C}^n} bezeichnen wir die {n}-dimensionalen Vektorräume und notieren die euklidschen Normen darauf mit {|x|} (was nicht zu Verwechselungen mit dem Betrag auf {{\mathbb R}} und {{\mathbb C}} führen sollte).

Die komplexe Konjugation von {z\in{\mathbb C}} bezeichnen wir mit {\overline{z}}, den Real- und Imaginärteil von {z} mit {\mathrm{Re}(z)} bzw. {\mathrm{Im}(z)}.

1.3. Literatur

Literatur zum Inhalt dieser Vorlesung gibt es reichlich, z.B.

  • Strampp, W., Voroztsov, E.V., Mathematische Methoden der Signalverarbeitung, Oldenbourg, 2004
  • Föllinger, O., Laplace-, Fourier- und {z}-Transformation, VDE-Verlag, 2011
  • Doetsch, G., Einführung in Theorie und Anwendung der Laplace-Transformation, Birkhäuser Verlag, 1958
  • Damelin, S.B., Miller, Jr., W., The Mathematics of Signal Processing, Cambridge University Press, 2012
  • Vich, R., {z}-Transformation: Theorie und Anwendung,Verlag Technik, 1964
  • Frey, T., Bossert, M., Signal- und Systemtheorie,Vieweg+Teubner, 2008.

2. Die {z}-Transformation

Die {z}-Transformation macht aus einem diskreten Signal eine holomorphe Funktion. Neben ihrer Anwendung auf diskrete Signale eignet sie sich auch zur Untersuchung von Differenzengleichungen.

Interpretieren wir den Index {n} einer Folge {(f_n)} als diskrete Zeit, so lassen sich diskrete Signale in Kategorien aufteilen: Die Signale die eine “Vergangenheit” haben und die, die nur “von jetzt ab” existieren und noch die, die “nur in der Vergangenheit” existieren.

Definition 1 (Kausale, antikausale und akausale Folgen) Eine zweiseitige Folge {(f_n)_{n\in{\mathbb Z}}} heißt kausal, wenn {f_n=0} für {n<0} gilt. Sie heißt antikausal, wenn {f_n=0} für {n\geq 0} gilt. Gilt keins von beiden, heißt sie akausal.

Eine (einseitige) Folge {(f_n)_{n\in{\mathbb N}}} bezeichnen wir ebenfalls als kausal.

2.1. Definition und elementare Eigenschaften

Definition 2 ({z}-Transformation) Für kausale Folge {f = (f_n)_{n\in{\mathbb N}}} definieren wir die {z}-Transformierteals

\displaystyle \mathcal{Z}(f)(z) = \sum_{n=0}^\infty f_n z^{-n}.

Die Abbildung {\mathcal{Z}} heißt {z}-Transformation. Für zweiseitige Folgen {(f_n)_{n\in{\mathbb Z}}} definieren wir analog die zweiseitige {z}-Transformationdurch

\displaystyle \mathcal{Z}_2(f)(z) = \sum_{n=-\infty}^\infty f_n z^{-n}.

In der Funktionentheorie haben wir gelernt, wie die Konvergenzbereiche von {z}-Transformierten aussehen:

Proposition 3 (Konvergenzgebiete von {z}-Transformierten) Zu einer Folge {(f_n)_{n\in{\mathbb N}}} existiert {r\geq 0}, so dass {\mathcal{Z}(f)} auf der Menge {\{z\in{\mathbb C}\ :\ r<|z|\}} absolut und lokal gleichmäßig konvergiert. Zu einer zweiseitigen Folge {(f_n)_{n\in{\mathbb Z}}} existieren {0\leq r\leq R}, so dass {\mathcal{Z}_2(f)} auf der Menge {\{z\in{\mathbb C}\ :\ r<|z|<R\}} absolut und lokal gleichmäßig konvergiert. Die Fälle {r,R=\infty} sind zugelassen und bedeuten, dass keine untere, bzw.~obere Schranke für {|z|} besteht.

Man beachte, dass der Fall {r=R} ein leeres Konvergenzgebiet bedeutet. Im Zusammenhang mit der zweiseitigen {z}-Tranformation nennt man den Teil {\sum_{n=0}^\infty f_n z^{-n}} den kausalen Teil (was bis auf den {0}-ten Term dem Hauptteil der Laurentreihe {\mathcal{Z}(f)} entspricht) und den Teil {\sum_{n=-\infty}^{-1} f_n z^{-n}} den antikausalen Teil. Das Konvergenzgebiet von {\mathcal{Z}(f)} ist genau der Schnitt der Konvergenzgebiete des kausalen und antikausalen Teils.

Proposition 4 Existieren für eine zweiseitige Folge {(f_n)_{n\in{\mathbb Z}}} Konstanten {C>0} und {0\leq a < b}, so dass für {n\geq 0} gilt

\displaystyle |f_n|\leq Ca^n,\quad |f_{-n}|\leq Cb^{-n},

dann Konvergiert {\mathcal{Z}(f)} für {a<|z|<b}.

Beweis:Aus {|f_n|\leq Ca^n} (für {n\geq 0}) folgt {\sqrt[n]{|f_n|}\leq \sqrt[n]{C} a} und daher auch

\displaystyle \limsup_{n\rightarrow\infty} \sqrt[n]{|f_n|} \leq a.

Die Potenzreihe {\sum_{n=0}^\infty f_n z^n} konvergiert nach dem Wurzelkriterium also für {|z|<1/a}, d.h. der kausale Teil von {\mathcal{Z}(f)} konvergiert für {|z|>a}. Ebenso sieht man, dass für {n\geq 0} gilt {\sqrt[n]{|f_{-n}|}\leq \sqrt[n]{C} b} und also auch {\limsup_{n\rightarrow\infty}\sqrt[n]{|f_{-n}|} \leq b^{-1}}. Die Potenzreihe {\sum_{n=1}^\infty f_{-n}z^n} (der antikausale Teil von {\mathcal{Z}(f)}) konvergiert also für {|z|<b}. \Box

Die Wachstumsbedingungen {|f_n|\leq Ca^n} und {|f_{-n}|\leq Cb^{-n}} ({n\geq 0}) garantieren bei {b>a} also die Konvergenz einer zweiseitigen {z}-Transformierten auf einem Kreisring in der komplexen Ebene. Natürlich konvergieren einseitige {z}-Transformierte außerhalb einer Kreisscheibe um den Nullpunkt bei entsprechenden Wachstumsbedingung.

Die {z}-Transformation ist unter anderem geeignet, um Differenzengleichungen zu lösen:

Beispiel 5 (Differenzengleichungen und die {z}-Transformation) Wir betrachten die berühmte Fibonacci-Folge {0,1,1,2,3,5,8,\dots}, welche rekursiv definiert ist:

\displaystyle f_0 = 0,\quad f_1 = 1,\quad f_{n+2} = f_{n+1} + f_n\quad\text{f\"ur } n\in{\mathbb N}. \ \ \ \ \ (1)

 

Natürlich lässt sich für jedes {n} der Wert von {f_n} rekursiv bestimmen. Unter einer “Lösung der Differenzengleichung (1)” verstehen wir allerdings eine explizite Darstellung von {f_n} in Abhängigkeit von {n}. Wir wollen nun beide Seiten von (1){z}-transformieren. Dazu definieren wir die Hilfsfolge {(g_n)} durch {g_n = f_{n+1}}, {n=0,1,\dots} und berechnen

\displaystyle \begin{array}{rcl} \mathcal{Z}(g)(z) & = & \sum_{n=0}^\infty g_n z^{-n} = \sum_{n=0}^\infty f_{n+1} z^{-n}\\ & =& \sum_{n=1}^\infty f_{n} z^{-(n-1)} = z\sum_{n=1}^\infty f_n z^{-n}\\ & = & z(Z(f)(z) - f_0). \end{array}

Ebenso berechnen wir für {h_n = f_{n+2}}

\displaystyle \mathcal{Z}(h)(z) = z^2(Z(f)(z) - f_0 - f_1z^{-1}).

Wir {z}-Transformieren nun die Gleichung (1)und erhalten (unter Benutzung der Werte {f_0=0} und {f_1=1})

\displaystyle z^2\Big(\mathcal{Z}(f)(z) - \frac1z\Big) = z\mathcal{Z}(f)(z) + \mathcal{Z}(f)(z)

was wir nach {\mathcal{Z}(f)} auflösen können

\displaystyle \mathcal{Z}(f)(z) = \frac{z}{z^2-z-1}.

An dieser Stelle müssen wir eine Folge {f} finden, die die Funktion {z/(z^2-z-1)} als {z}-Transformierte hat. Mit Hilfe der Funktionentheorie ist dies möglich. Wir unterbrechen das Beispiel kurz, für einen Satz, der die Koeffizienten einer {z}-Transformierten angibt.

Satz 6 (Umkehrung der {z}-Transformation) Es gelte {F(z) = \sum_{n=0}^\infty f_n z^{-n}} für {0\leq r<|z|} und es sei {\rho>r}. Dann gilt

\displaystyle f_n = \frac{1}{2\pi\mathrm{i}} \int_{|z|=\rho} F(z)z^{n-1}{\mathrm d}{z},\quad n\geq 0,

das heißt, die Folge {(f_n)} wird durch die {z}-Transformation in {F(z)} überführt. Außerdem ist {(f_n)} die einzige solche Folge.

Beweis:Die {z}-Transformierte der Folge {(f_n)} ist

\displaystyle \mathcal{Z}(f)(z) = \sum_{n=0}^\infty f_n z^{-n}.

Wir multiplizieren diese Gleichung mit {z^{k-1}} und integrieren beide Seiten über die Kreislinie {|z|=\rho}: Da wir auf Grund der gleichmäßigen Konvergenz entlang des Weges gliedweise Integrieren dürfen ergibt sich

\displaystyle \int_{|z|=\rho} z^{k-1}\mathcal{Z}(f)(z){\mathrm d}{z} = \sum_{n=0}^\infty f_n \int_{|z|=\rho} z^{-n+k-1}{\mathrm d}{z}.

Mit

\displaystyle \int_{|z|=\rho} z^{-n+k-1}{\mathrm d}{z} = \begin{cases} 2\pi\mathrm{i} & \text{für} -n+k-1=-1\\ 0 & \text{sonst.} \end{cases}

folgt {\mathcal{Z}(f) = F}. Die Eindeutigkeit der Folge {(f_n)} ist analog zur Eindeutigkeit der Taylor-Koeffizienten. \Box

Beispiel 7 (Fortsetzung des Fibonacci-Beispiels) Wir müssen also die Funktion {F(z) = z/(z^2-z-1)} betrachten. Es liegen zwei Pole vor die wir als Nullstellen {z_1,z_2} des Nenners berechnen:

\displaystyle z^2-z-1 = 0\quad\leadsto\quad z_1 = \frac{1-\sqrt{5}}{2},\quad z_2 = \frac{1+\sqrt{5}}{2}.

Wir benutzen nun Satz~6und wählen ein {\rho>\max(|z_1|,|z_2|)} und berechnen

\displaystyle f_n = \frac{1}{2\pi\mathrm{i}}\int_{|z|=\rho} F(z)z^{n-1}{\mathrm d}{z} = \frac{1}{2\pi\mathrm{i}}\int_{|z|=\rho} \frac{z^{n}}{(z-z_1)(z-z_2)}{\mathrm d}{z}

Mit dem Residuensatz bekommen wir

\displaystyle f_n = \mathrm{Res}_{z_1} \frac{z^{n}}{(z-z_1)(z-z_2)} + \mathrm{Res}_{z_2} \frac{z^{n}}{(z-z_1)(z-z_2)} = \frac{z_1^n - z_2^n}{z_2-z_1}.

Explizit erhalten wir die geschlossene Form der {n}-ten Fibonacci-Zahl

\displaystyle f_n = \frac{(1+\sqrt{5})^n - (1-\sqrt{5})^n}{2^n\sqrt{5}}.

Diese Formel ist auch unter dem Namen “Formel von Moivre-Binet” bekannt. (Ein anderer Beweis dieser Formel stellt die Fibonacci-Folge durch Matrix-Potenzen dar und benutzt die Diagonalisierung der Matrix zur expliziten Darstellung der Einträge der Potenzen.)

Am Beispiel der Fibonacci-Folge haben wir nicht nur die Umkehrformel aus Satz~6, sonder auch schon deren Linearität und einen “Verschiebungssatz” benutzt. Wir sammeln diese und weitere solcher Eigenschaften im folgenden Satz:

Satz 8 (Elementare Eigenschaften der einseitigen {z}-Transformation) Die {z}-Transformierte der Folge {(f_n)_{n\in{\mathbb N}}} habe den Konvergenzbereich {\{|z|>r\}}. Für die einseitige {z}-Transformation gilt:

  • Linearität: Für Folgen {(f_n)_{n\in{\mathbb N}}} und {(g_n)_{n\in{\mathbb N}}} und {c\in{\mathbb C}} gilt

    \displaystyle \mathcal{Z}(f+cg)(z) = \mathcal{Z}(f)(z) + c\mathcal{Z}(g)(z)

    falls {z} in beiden Konvergenzbereichen von {\mathcal{Z}(f)} und {\mathcal{Z}(g)} liegt.

  • Konjugation: Es gilt

    \displaystyle \mathcal{Z}(\overline{f})(z) = \overline{\mathcal{Z}(f)(\overline{z})}.

  • Dämpfung: Für {(f_n)_{n\in{\mathbb N}}} , {\gamma\in{\mathbb C}} und mit {g_n = \gamma^n f_n} gilt für {|z|>|\gamma|r}

    \displaystyle \mathcal{Z}(g)(z) = \mathcal{Z}(f)(\gamma^{-1} z).

  • Differentiation: Für {g_n = n f_n} und {|z|>r} gilt

    \displaystyle \mathcal{Z}(g)(z) = -z\frac{{\mathrm d}{}}{{\mathrm d}{z}}\mathcal{Z}(f)(z).

  • Linksverschiebung: Für {k\in{\mathbb N}}, {k>0} setze {g_n = f_{n+k}}, {n\in{\mathbb N}} (also {g = (f_k,f_{k+1},\dots)}). Dann gilt für {|z|>r}

    \displaystyle \mathcal{Z}(g)(z) = z^k(\mathcal{Z}(f)(z) - \sum_{n=0}^{k-1} f_n z^{-n}).

  • Rechtsverschiebung: Für {k\in{\mathbb N}}, {k>0} setze

    \displaystyle g_n = \begin{cases} 0 & \text{falls}\ n<k\\ f_{n-k} & \text{sonst.} \end{cases}

    (also {g = (0,\dots,0,f_0,f_1,\dots)}). Dann gilt für {|z|>r}

    \displaystyle \mathcal{Z}(g)(z) = z^{-k}\mathcal{Z}(f)(z).

 

Beweis:

  • Linearität folgt aus der Linearität der Reihenbildung.
  • Dämpfung rechnet man direkt nach:

    \displaystyle \mathcal{Z}(g)(z) = \sum_{n=0}^\infty f_n \gamma^n z^{-n} = \mathcal{Z}(f)(\gamma^{-1} z).

  • Konjugation rechnet man ebenso direkt.
  • Differentiation zeigt man, indem man mit {\frac{{\mathrm d}{}}{{\mathrm d}{z}}\mathcal{Z}(f)} startet und Differentiation mit der Reihenbildung vertauscht (lokal gleichmäßige Konvergenz!):

    \displaystyle \frac{{\mathrm d}{}}{{\mathrm d}{z}}\mathcal{Z}(f)(z) = \sum_{n=0}^\infty f_n (-n)z^{-n-1} = -z^{-1}\sum_{n=0}^\infty nf_n z^{-n} = z^{-1}\mathcal{Z}(g)(z).

    Beachte noch, dass gliedweise Differentiation den Konvegrenzbereich unverändert lässt.

  • Linksverschiebung rechnet man wie folgt nach:

    \displaystyle \mathcal{Z}(g)(z) = \sum_{n=k}^\infty f_nz^{-n+k} = z^k(\mathcal{Z}(f)(z) - \sum_{n=0}^{k-1} f_n z^{-n}).

  • Rechtsverschiebung geht noch ein bisschen einfacher:

    \displaystyle \mathcal{Z}(g)(z) = \sum_{n=k}^\infty f_{n-k}z^{-n} = z^{-k}\sum_{n=0}^\infty f_{n}z^{-n} = z^{-k}\mathcal{Z}(f)(z).

    \Box

    Für die zweiseitige Transformation gelten analoge Regeln, nur bei der Verschiebung wird es einfacher und wir können die “Zeit” {n} umkehren:

    Satz 9 (Weitere Regeln für die zweiseitige {z}-Transformation) Die {z}-Transformierte der zweiseitigen Folge {(f_n)_{n\in{\mathbb Z}}} konvergiere für {r<|z| < R}. Dann gilt:

  • Verschiebung: Für {k\in{\mathbb Z}} setze {g_n = f_{n-k}}. Dann gilt für {r<|z|<R}

    \displaystyle \mathcal{Z}_2(g)(z) = z^{-k}\mathcal{Z}_2(f)(z).

  • Zeitumkehr: Mit {g_n = f_{-n}} gilt für {\tfrac{1}{R}<|z|<\tfrac1r}

    \displaystyle \mathcal{Z}_2(g)(z) = \mathcal{Z}_2(f)(\tfrac{1}{z}).

     

  •  

    Beweis: In beiden Fällen sind das elementare Rechnungen, die sich zur Übung lohnen. \Box

    2.2. Rechenbeispiele

    Wir werden im Folgenden häufig die etwas laxe Schreibweise {\mathcal{Z}(f_n)(z)} anstelle von {\mathcal{Z}(f)(z)} benutzen, d.h. anstelle der Folge {f} setzen wir “das {n}-te Folgenglied” ein. Das erspart ein wenig Schreibarbeit und ist manchmal klarer. So wir die Dämpfungsregel zum Beispiel zu

    \displaystyle \mathcal{Z}(\gamma^n f_n)(z) = \mathcal{Z}(f)(\gamma^{-1}z).

    Beispiel 10 (“Einheitssprung”) In der Signalverarbeitung ist der Einheitssprung die Folge, die bei {n=0} vom Wert Null auf Eins springt, d.h.

    \displaystyle f_n = \begin{cases} 0 & \text{für}\ n<0\\ 1 & \text{für}\ n\geq 1. \end{cases}

    Die zweiseitige {z}-Transformierte des Einheitssprunges ist

    \displaystyle \mathcal{Z}_2(f)(z) = \sum_{n=0}^\infty z^{-n} = \frac{1}{1-1/z} = \frac{z}{z-1}.

    Die ist ebenfalls die einseitige {z}-Transformierte der konstanten Folge {f_n=1}, {n\in{\mathbb N}}, d.h. {\mathcal{Z}(1)(z) = z/(z-1)}.

    Beispiel 11 (Komplexe Exponentialfolge) Zu {\gamma\in{\mathbb C}} schließen wir mit der Dämpfungsregel und dem vorherigen Beispiel

    \displaystyle \mathcal{Z}(\gamma^n)(z) = \frac{\gamma^{-1}z}{\gamma^{-1}z -1} = \frac{z}{z-\gamma}.

    Beispiel 12 (Einsatz der Ableitungsregel) Wegen

    \displaystyle \frac{{\mathrm d}}{{\mathrm d}{z}}\mathcal{Z}(1)(z) = \frac{{\mathrm d}{}}{{\mathrm d}{z}}\Big(\frac{z}{z-1}\Big) = -\frac{1}{(z-1)^2}

    schließen wir (wieder aus der bekannten Transformierten des Einheitssprunges)

    \displaystyle \mathcal{Z}(n)(z) = \frac{z}{(z-1)^2}.

    Beispiel 13 Zu {a,b\in{\mathbb C}} mit {a\neq 0} suchen wir die Urbildfolge zur {z}-Transformierten

    \displaystyle \mathcal{Z}(f)(z) = \frac{b}{z-a}.

    Es gilt

    \displaystyle \frac{b}{z-a} = bz^{-1}\frac{z}{z-a}.

    Wir wissen schon {\mathcal{Z}(a^n) = z/(z-a)} und schließen mit der Linearität und der Regel für die Rechtsverschiebung

    \displaystyle f_n = \begin{cases} 0 & \text{für}\ n=0\\ ba^{n-1} & \text{für}\ n\geq 1. \end{cases}

    2.3. Faltungssatz und Anwendung

    Definition 14 Für zwei zweiseitige Folgen {(f_n)_{n\in{\mathbb Z}}} und {(g_n)_{n\in{\mathbb Z}}} ist die Faltungvon {f} und {g} definiert durch

    \displaystyle (f*g)_n = \sum_{\nu=-\infty}^\infty f_\nu g_{n-\nu}

    (wann immer die Reihe konvergiert).

    Bemerkung 15 Die Konvergenz der Reihe in der Definition der Faltung ist unter vielen verschiedenen Umständen gesichert (zum Beispiel, falls eine Folge absolut summiertbar ist, muss die andere nur beschränkt sein und ein Wachstum der einen Folge für {n\rightarrow\pm\infty} kann durch entsprechenden Abfall der anderen Folge ausgeglichen werden). Sind die beiden Folgen {f} und {g} zum Beispiel absolut summierbar, so ist auch {f*g} absolut summierbar, denn

    \displaystyle \sum_n |f*g|_n \leq\sum_n\Big(\sum_\nu|f_\nu|\,|g_{n-\nu}|\Big) = \Big(\sum_\nu |f_\nu|\Big)\Big(\sum_n |g_n|\Big).

    Weiterhin sieht man durch Indexsubstitution, dass die Faltung eine kommutative Operation ist:

    \displaystyle (f*g)_n = \sum_{\nu=-\infty}^\infty f_\nu g_{n-\nu} = \sum_{k=-\infty}^\infty f_{n-k} g_k = (g*f)_n.

    Assoziativität ist nicht immer erfüllt. Um dies zu sehen, betrachten wir {(f*g)*h} und {f*(g*h)}:

    \displaystyle \begin{array}{rcl} ((f*g)*h)_n = \sum_\nu (f*g)_\nu*h_{n-\nu} = \sum_\nu\sum_k f_k g_{\nu-k} h_{n-\nu} \end{array}

    \displaystyle \begin{array}{rcl} (f*(g*h))_n & = & \sum_k f_k(g*h)_{n-k} = \sum_kf_k \sum_l g_l h_{n-k-l}\\ & = & \sum_kf_k \sum_\nu g_{\nu-k} h_{n-\nu}.. \end{array}

    Beide Ausdrücke sind gleich falls wir die Reihen vertauschen dürfen, was zum Beispiel für absolut summierbare Folgen {f}, {g} und {h} der Fall ist. Es zeigt sich also, dass sich absolut summierbare Folgen gut mit der Faltung vertragen. Wir führen daher ein:

    \displaystyle \ell^1({\mathbb Z}) = \{ (f_n)_{n\in{\mathbb Z}}\ :\ \sum_n |f_n|<\infty\}.

    Der Raum {\ell^1({\mathbb Z})} ist ein Vektorraum der üblicherweise mit der Norm {\|f\|_{\ell^1} = \sum_n |f_n|} versehen wird; damit wird er zum normierten Raum (und, da er vollständig ist, sogar zum Banach-Raum). Die Faltung erfüllt auch ein Distributivgesetz, so dass wir festhalten können: {\ell^1({\mathbb Z})} bildet mit der Addition und der Faltung als Produkt eine kommutative und assoziative Algebra. Es gibt hier auch ein Einselement {e}, d.h. ein neutrales Element bzgl. der Faltung, nämlich

    \displaystyle e_n = \delta_{n,0}.

    Beispiel 16 Falten mit

    \displaystyle h_n = \delta_{n,n_0} = \begin{cases} 1 &\text{für }\ n=n_0\\ 0 &\text{sonst.} \end{cases}

    verschiebt das Signal:

    \displaystyle (f*h)_n = \sum_{\nu=-\infty}^\infty f_\nu h_{n-\nu} = f_{n-n_0}.

    Falten mit

    \displaystyle h_n = \begin{cases} 1/(2n_0+1) &\text{für }\ n=-n_0,\dots,n_0\\ 0 &\text{sonst.} \end{cases}

    bildet einen lokalen Mittelwert über die {2n_0+1} Nachbarn:

    \displaystyle (f*h)_n = \sum_{\nu=-\infty}^\infty f_\nu h_{n-\nu} = \frac{1}{2n_0+1}\sum_{\nu=-n_0}^{n_0} f_{n-\nu}.

    Filtern mit dem Einheitssprung {h} (aus Beispiel 10) liefert eine kumulative Summe:

    \displaystyle (f*h)_n = \sum_{\nu=-\infty}^\infty f_\nu h_{n-\nu} = \sum_{\nu\leq n} f_\nu.

    Ist die Faltung eine umkehrbare Operation? Das heißt, kann man die Gleichung {g = f*h} nach {f} auflösen? Anders gesagt: Gibt es zu {h} ein “Faltungsinverses”? Im Allgemeinen nicht, aber wann das geht, kann man mit Hilfe des Faltungssatzes erkennen.

    Der Faltungssatz für die {z}-Transformation sagt, dass die {z}-Transformation die Faltung in eine punktweise Multiplikation überführt:

    Satz 17 (Faltungssatz für die {z}-Transformation, zweiseitig) Die (zweiseitigen) {z}-Transformierten der zweiseitigen Folgen {(f_n)_{n\in{\mathbb Z}}} und {(g_n)_{n\in{\mathbb Z}}} konvergieren für {r<|z|<R}. Dann gilt ebenfalls für {r<|z|<R}

    \displaystyle \mathcal{Z}_2(f*g)(z) = \mathcal{Z}_2(f)(z)\mathcal{Z}_2(g)(z).

    Beweis:Wir beginnen von der rechten Seite. Da die jeweiligen Reihen absolut konvergieren, können wir umsortieren:

    \displaystyle \begin{array}{rcl} \mathcal{Z}_2(f)(z)\mathcal{Z}_2(g)(z) & = & \sum_{n=-\infty}^\infty f_nz^{-n}\sum_{\nu=-\infty}^\infty g_\nu z^{-\nu}\\ & = & \sum_{n=-\infty}^\infty\sum_{\nu=-\infty}^\infty f_n g_\nu z^{-(n+\nu)}\\ & = & \sum_{n=-\infty}^\infty\sum_{k=-\infty}^\infty f_n g_{k-n} z^{-k}\\ & = & \sum_{k=-\infty}^\infty\Big(\sum_{n=-\infty}^\infty f_n g_{k-n}\Big) z^{-k}\\ & = & \mathcal{Z}_2(f*g)(z). \end{array}

    \Box

    Setzen wir kausale Folgen im Faltungssatz sein, erhalten wir den Spezialfall für einseitige Folgen:

    Korollar 18 (Faltungssatz für die {z}-Transformation, einseitig) Die {z}-Transformierten der Folgen {(f_n)_{n\in{\mathbb N}}} und {(g_n)_{n\in{\mathbb N}}} konvergieren für {r<|z|}. Dann gilt mit der Definition

    \displaystyle (f*g)_n = \sum_{\nu=0}^n f_\nu g_{n-\nu}

    ebenfalls für {r<|z|}

    \displaystyle \mathcal{Z}(f*g)(z) = \mathcal{Z}(f)(z)\mathcal{Z}(g)(z).

    Beispiel 19 (Entfaltung) Es seien {f} und {h} zweiseitige Folgen und {g = f*h}. Nach {z}-Transformation können wir die Gleichung formal nach {\mathcal{Z}_2(f)} auflösen, denn nach dem Faltungssatz gilt {\mathcal{Z}_2(g) = \mathcal{Z}_2(f)\,\mathcal{Z}_2(h)} und daher {\mathcal{Z}_2(f) = \mathcal{Z}_2(g)/\mathcal{Z}_2(h)}. Wir nehmen nun an, dass das Konvergenzgebiet von {\mathcal{Z}(h)} jenes von {\mathcal{Z}_2(g)} umfasst (welches wir als {r<|z|<R} annehmen). Hat nun {\mathcal{Z}_2(h)} keine Nullstellen in {r<|z|<R}, so ist {\mathcal{Z}_2(g)/\mathcal{Z}_2(h)} dort komplex differenzierbar (insbesondere hat es keine Pole). In der Tat handelt es sich bei {\mathcal{Z}_2(g)/\mathcal{Z}_2(h)} um eine {z}-Transformierte. Unter Umständen handelt es sich bei {1/\mathcal{Z}_2(h)} auch um eine {z}-Transformierte; die zugehörige Folge könnte man dann als “Faltungsinverse” von {h} bezeichnen. Wir machen dies an einem Beispiel konkret: Wir betrachten die Faltung mit dem Einheitssprung {h} (Beispiel 10). Dieser hat die {z}-Transformierte

    \displaystyle \mathcal{Z}_2(h)(z) = \frac{z}{z-1}.

    Der Kehrwert davon ist

    \displaystyle \frac{1}{\mathcal{Z}_2(h)(z)} = \frac{z-1}{z} = 1 - \frac{1}{z}.

    Die inverse {z}-Transformierte davon lässt sich aus bekannten {z}-Transformierten bestimmen oder raten: Es gilt

    \displaystyle \mathcal{Z}(\delta_{n,0})(z) = \sum_{n\in{\mathbb Z}}\delta_{n,0} z^{-n} = 1

    und

    \displaystyle \mathcal{Z}(\delta_{n,1})(z) = \sum_{n\in{\mathbb Z}}\delta_{n,1} z^{-n} = \frac{1}{z}.

    Die inverse {z}-Transformierte von {1/\mathcal{Z}_2(h)} ist also {\delta_{n,0} - \delta_{n,1}}.

    2.4. Differenzengleichungen

    Nun behandeln wir noch das Lösen von Differenzengleichungen etwas ausführlicher. Zuerst definieren wir Differenzen und Partialsummen von Folgen und geben dann Rechenregeln für die zugehörigen {z}-Transformierten an:

    Definition 20 Zu einer Folge {(f_n)_{n\in{\mathbb N}}} definieren wir die erste Differenz {(\Delta f)_n = f_{n+1}-f_n}, {n\in{\mathbb N}} und die Partialsumme {(\Sigma f)_n = \sum_{\nu=0}^n f_\nu}.

    Satz 21 Die {z}-Transformierte von {(f_n)} konvergiere für {|z|>r}. Es gilt

    \displaystyle \mathcal{Z}(\Delta f) = (z-1)\mathcal{Z}(f)(z) - f_0 z

    (und konvergiert ebenfalls für {|z|>r}) und

    \displaystyle \mathcal{Z}(\Sigma f)(z) = \frac{z}{z-1}\mathcal{Z}(f)(z)

    (und konvergiert für {|z|>\max(1,r)})

    Beweis:Die erste Gleichung folgt aus der Regel für die Linksverschiebung und der Linearität

    \displaystyle \begin{array}{rcl} \mathcal{Z}(\Delta f)(z) & =& \mathcal{Z}(f_{n+1})(z) - \mathcal{Z}(f_n)(z)\\ & = & z(\mathcal{Z}(f_n)(z) - f_0) - \mathcal{Z}(f_n)(z)\\ & =& (z-1)\mathcal{Z}(f_n)(z) - zf_0. \end{array}

    Für die zweite Gleichung rechnen wir direkt

    \displaystyle \begin{array}{rcl} \mathcal{Z}(\Sigma f)(z) &=& \sum_{n=0}^\infty \Big(\sum_{\nu=0}^n f_\nu\Big)z^{-n}\\ & = & \hphantom{+}f_0z^0\\ & & +(f_0 + f_1)z^1\\ & & +(f_0 + f_1 + f_2)z^2\\ & & +\dots\\ & = & \sum_{\nu=0}^\infty\sum_{n=0}^\infty f_n z^{-n-\nu}\\ & = & \sum_{\nu=0}^\infty z^{-\nu}\mathcal{Z}(f)(z) = \frac{z}{z-1}\mathcal{Z}(f)(z). \end{array}

    Bemerke, dass die mittlere Doppelreihe (und somit auch die anderen Ausdrücke) absolut und lokal gleichmäßig konvergieren für {|z|>\max(1,r)}. \Box

    Der Differenzenoperator und der Partialsummenoperator entsprechen grob der Ableitung und dem Integral für Funktionen auf der reellen Achse.

    Beispiel 22 (Differenz und Ableitung) Ist eine Folge durch “Abtasten” einer Funktion {f:{\mathbb R}\rightarrow{\mathbb C}} mit “Abtastrate” {\tau>0} gegeben, so schreiben wir (unter Missbrauch der Notation) {f_n = f(\tau n)}. Dann gilt

    \displaystyle \frac{\Delta f_n}{\tau} = \frac{f_{n+1} - f_n}{\tau} = \frac{f(\tau n + \tau) - f(\tau n)}{\tau}.

    Für {\tau\rightarrow 0} (mit der Kopplung {\tau n = x}) konvergiert die rechte Seite gegen {f'(x)}. Wir betrachten nun die Differenzengleichung

    \displaystyle (\Delta f)_n = \tau f_n

    und berechnen die Lösung mit Hilfe der {z}-Transformation. Es ergibt sich

    \displaystyle (z-1)\mathcal{Z}(f)(z) - zf_0 = \tau\mathcal{Z}(f)(z)

    und daher

    \displaystyle \mathcal{Z}(f) = \frac{zf_0}{z - (1+\tau)}.

    Die Lösung ist also

    \displaystyle f_n = f_0(1+\tau)^n.

    Im Grenzwert {\tau\rightarrow 0} (wieder bei Kopplung {\tau n = x}) erhalten wir den Grenzwert {\exp(x)} wie es auch zu erwarten wäre.

    Lineare Differenzengleichung (auch höherer Ordnung) lassen sich prinzipiell mit Hilfe der {z}-Transformation lösen. Hier noch ein paar Beispiele:

    Beispiel 23

    1. Wir betrachten

      \displaystyle f_{n+2} + f_{n+1} - 2f_n = 1

      mit {f_0=0} und {f_1 = 1}. {z}-Transformation ergibt

      \displaystyle z^2(\mathcal{Z}(f)(z) - f_0 - f_1/z) + z(\mathcal{Z}(f)(z) - f_0) -2\mathcal{Z}(f)(z) = \frac{z}{z-1}

      also

      \displaystyle \frac{z}{z-1} = (z^2 + z - 2)\mathcal{Z}(f)(z) - z = (z-1)(z+2)\mathcal{Z}(f)(z) - z

      damit

      \displaystyle \mathcal{Z}(f)(z) = \frac{z^2}{(z-1)^2(z+2)}.

      Um die inverse {z}-Transformierte zu bestimmen, benutzen wir die Partialbruchzerlegung {\frac{z}{(z-1)^2(z+2)} = \frac{2}{9(z-1)} + \frac{1}{3(z-1)^2} - \frac{2}{9(z+2)}} und bekommen

      \displaystyle \mathcal{Z}(f)(z) = \frac{2z}{9(z-1)} + \frac{z}{3(z-1)^2} - \frac{2z}{9(z+2)}.

      Die invers {z}-Transformierten lassen sich nun ablesen:

      \displaystyle f_n = \frac{2}{9} + \frac{1}{3} k - \frac{2}{9}(-2)^k.

       

    2. Als weiteres Beispiel betrachten wir

      \displaystyle f_{n+3} - 3f_{n+2} + 4f_n = 1

      mit den Anfangsbedingungen { f_0=f_1=f_2=0}. {z}-Transformation ergibt

      \displaystyle z^3\mathcal{Z}(f)(z) - 3z^2\mathcal{Z}(f)(z) +4\mathcal{Z}(f)(z) = \frac{z}{z-1}

      also (nach Bestimmung der Nullstellen von {z^3-3z^2+4})

      \displaystyle \mathcal{Z}(f)(z) = \frac{z}{(z-1)(z-2)^2(z+1)}.

      Partialbruchzerlegung von {1/((z-1)(z-2)^2(z+1))} gibt

      \displaystyle \frac{z}{(z-1)(z-2)^2(z+1)} = \frac{z}{2(z-1)} - \frac{z}{18(z+1)} - \frac{4z}{9(z-2)} + \frac{z}{3(z-2)^2}.

      und mit Hilfe von bekannten {z}-Transformierten und den Rechenregeln können wir die Lösung ablesen:

      \displaystyle f_n = \frac{1}{2} - \frac{1}{18}(-1)^n - \frac{4}{9}2^n + \frac{1}{3}n2^{n-1}.

     

    2.5. Zur Umkehrung der {z}-Transformation

    In Satz~6haben wir ein Ergebnis zur Umkehrung der einseitigen {z}-Transformation formuliert: Ist {F(z)} die {z}-Transformierte von {(f_n)_{n\in{\mathbb N}}} mit Konvergenzgebiet {|z|>r}, dann gilt für jedes {\rho>r}

    \displaystyle f_n = \frac{1}{2\pi\mathrm{i}}\int_{|z|=\rho}F(z)z^{n-1}{\mathrm d}{z}.

    Für die zweiseitige {z}-Transformierte ist die Situation ein klein wenig komplizierter, und es stellt sich heraus, dass es zu einer Funktion {F} durchaus mehrere Folgen geben kann, deren {z}-Transformierte sie ist. Der Grund dafür sind die etwas komplizierteren Konvergenzgebiete, die bei der zweiseitigen Transformation aus Kreisringen und nicht aus Komplementen von Kreisen bestehen.

    Wir betrachten ein Beispiel:

    Beispiel 24 Es sei

    \displaystyle F(z) = \frac{2z^2-3z}{z^2-3z+2}.

    Der Nenner hat die Nullstellen {z_1=1} und {z_2=2}. Es gibt nun drei Möglichkeiten, ein Konvergenzgebiet festzulegen, nämlich:

    1. {|z|>2},
    2. {1<|z|<2} und
    3. {0<|z|<1}.

    Jedes Konvergenzgebiet gehört zu einer anderen zweiseitigen Folge. Um diese Folgen zu berechnen, zerlegen wir {F} als

    \displaystyle F(z) = \frac{z}{z-1} + \frac{z}{z-2}.

    Wir entwickeln die Summanden {z/(z-c)} nun auf zwei verschiedene Arten in Reihen: Einerseits ist

    \displaystyle \frac{z}{z-c} = \sum_{n=0}^\infty c^nz^{-n} \ \ \ \ \ (2)

     

    und andererseits gilt

    \displaystyle \frac{z}{z-c} = -\frac{z}{c}\,\frac{1}{1 - \tfrac{z}{c}} = -\frac{z}{c}\sum_{n=0}^\infty \Big(\frac{z}{c}\Big)^n = -\sum_{n=-1}^{-\infty} \Big(\frac{z}{c}\Big)^{-n}. \ \ \ \ \ (3)

     

    Die erste Reihe konvergiert für {|z|>c}, die zweite für {0<|z|<c}. Für beide Summanden haben wir jeweils zwei Möglichkeit, wobei eine auf ein leeres Konvergenzgebiet führt ({|z|>2} und {|z|<1}). Die relevanten drei Möglichkeiten ergeben:

    1. Wählen wir jeweils die Variante (2), so ergibt sich für {|z|>2}:

      \displaystyle F(z) = \sum_{n=0}^\infty z^{-n} + \sum_{n=0}^\infty 2^n z^{-n},

      also

      \displaystyle f_n = \begin{cases} 0 & n<0\\ 1 + 2^n & n\geq 0 \end{cases}

      bzw.

      \displaystyle f = (\dots,0,\underline{2},3,5,9,17,\dots).

       

    2. Im Konvergenzgebiet {1<|z|<2} ergibt sich

      \displaystyle F(z) = \sum_{n=0}^\infty z^{-n} - \sum_{n=-\infty}^{-1} 2^nz^{-n}

      also

      \displaystyle f_n = \begin{cases} -2^n & n\leq -1\\ 1 & n\geq 0 \end{cases}

      bzw.

      \displaystyle f = ( \dots, -\tfrac18,-\tfrac14,-\tfrac12,\underline{1},1,1,1,\dots).

       

    3. Wählen wir beide Male die Variante (3)ergibt sich im Konvergenzgebiet {0<|z|<1}:

      \displaystyle F(z) = -\sum_{n=-\infty}^{-1} z^{-n} - \sum_{n=-\infty}^{-1} 2^nz^{-n}

      also

      \displaystyle f_n = \begin{cases} -1- 2^n & n\leq -1\\ 0 & n\geq 0 \end{cases}

      bzw.

      \displaystyle f = ( \dots, -1-\tfrac18,-1-\tfrac14,-1-\tfrac12,\underline{0},0,0,0,\dots).

    Wir halten fest: Für eine gegebene Funktion {F:{\mathbb C}\rightarrow{\mathbb C}} erhalten wir eine Invers-{z}-Transformierte indem wir einen Kreisring wählen, in dem {F} komplex differenzierbar ist (insbesondere ohne Polstellen und wesentliche Singularitäten). Für einen Kreislinie mit Radius {\rho} die sich ganz im Inneren des Kreisrings befindet ergibt die Formel

    \displaystyle f_n = \frac{1}{2\pi\mathrm{i}}\int_{|z|=\rho}F(z)z^{n-1}{\mathrm d}{z}.

    die Folgenglieder der Invers-{z}-Transformierten. Dass diese Formel für verschiedene Radien {\rho} verschiedene Ergebnisse liefert liegt daran, dass das Integral nach dem Residuensatz den Residuendes Integranden innerhalb der Kreislinie entspricht; in Formeln:

    \displaystyle f_n = \frac{1}{2\pi\mathrm{i}}\int_{|z|=\rho}F(z)z^{n-1}{\mathrm d}{z} = \sum_{|\zeta|\leq\rho}\mathrm{Res}_{\zeta}F(z)z^{n-1}.

    Für Berechnungen lohnt es sich oft auf bekannte {z}-Transformierte zurückzugreifen, man muss dabei jedoch die Konvergenzgebiete entsprechend berücksichtigen.

    2.6. Abschlussbemerkungen

    Wir schließen die Behandlung der {z}-Transformation mit einigen Bemerkungen ab:

    1. Die {z}-Transformation hat einen Verwandten in der Mathematik: Die sogenannte erzeugende Funktioneiner Folge {(a_n)_{n\in{\mathbb N}}}. Diese ist

      \displaystyle f(z) = \sum_{n=0}^\infty a_n z^n.

      Sie unterscheidet sich von der {z}-Transformierte nur im den Exponenten des {z} und es gilt {f(z) = \mathcal{Z}(a)(1/z)}. Sie hat vielerlei Anwendungen in der Kombinatorik und auch in der Wahrscheinlichkeitsrechnung.

    2. Die {z}-Transformierte wird auf Folgen angewendet und lässt sich für zum Beispiel für digitale Signale und für Differenzengleichungen einsetzen. Die Erweiterung auf Funktionen (d.h. analoge Signale) wird die Laplace-Transformation sein (mit welcher dann z.B. Differentialgleichungen gelöst werden können).
    3. Von besonderem Interesse sind beschränkte Folgen (in der Signalverarbeitung sind unbeschränkte Folgen als Signale nicht relevant). Zweiseitige beschränkte Folgen können durchaus ein leeres Konvergenzgebiet haben (wie schon das einfache Beispiel {f_n\equiv 1} zeigt) Sind {r=R=1} so kann entlang des “kritischen Kreises” {|z|=1} keine Aussage über die Konvergenz getroffen werden. Mit Hilfe von Fourier-Reihen werden wir diese Situation weiter untersuchen.

 

It feels a bit awkward to write this post this very evening but, however, I planned to write it and so I’ll do…

I’ve been to some job interviews for lately (three to be precise). In all three interviews it happened that I was asked a question I did not prepare an answer for (although I had heard this question before and should have known that it’ll be asked). Hence, I thought it could be helpful to collect some standard questions here.

Probably I should add that I am talking about job interviews for professorships in mathematics in Germany. When I looked around on the web for tips and tricks for job interviews, I found a lot of tips for the US market. Most of the tips seem to apply to the German situation but I had the feeling that a post specifically for Germany could help.

When you apply for a professorship in Germany you send your documents as requested – usually that is:

  • Your CV.
  • Your list of publications.
  • Your teaching record.
  • A list of your projects (third party funded).
  • A cover letter.
  • A copy of your PhD certificate.

I have everything but the cover letter and the certificate within the CV. Sometimes you’ll be asked to send some kind of “teaching statement” or “research statement” and sometimes they ask for evaluation sheets of lectures. Recently I’ve seen more advertisements that directly say that they want digital applications via email.

Respect the deadline! Once the deadline has passed you have to wait. If the committee is quick and you’re lucky you’ll hear something after a few weeks (two or three, say); if you do not hear anything for more than six weeks, you are probably out of the game. In case you are lucky you will be invited for a job interview (sometimes by email, sometimes by snail mail and sometimes by phone). Usually there will be five to seven people invited. The job interview always takes place at the university you applied to (I think – I have never been asked for a phone or Skype interview). It always consists of

  • research talk (between 30 and 45 minutes) and
  • the actual interview with the committee.

Sometimes you will be asked to

  • give a lecture for students

and I was once told that there will be an interview by students. It never happened to me that special meetings with other faculty, the dean or anybody else were planned neither I had special campus tours.

I will focus on the job interview here. Usually, the committee consists of some math professors (three to six or so), a PostDoc or PhD student, some students (about two) and some member of the non-scientific staff. Moreover, it may happen that some member of the university board is present.

The question almost always follow the general guideline: Research, projects, cooperation, teaching, administration.

  • What are your next goals for your research? Variations are: Where to do you see yourself and your research in five or ten years? What are the important issues in your field? Here you can use what you have talked about in your research talk (and you can prepare your talk such that it helps you here). Have something concrete and some more general vision.
  • What was your motivation to apply for this position? You should have a good reason (different from “I apply to every position I can find.”) and you should tell the commitee.
  • What are your experiences with third party funding? Usually the committee would like to hear that you know where to get money for research and that you know how that works.
  • What possibilities for cooperation do you see? I think this is a crucial point and I often put some effort in to find out what is happening in the math department, in computer science, in physics and in the engineering department. However, I think that it is quite difficult to judge if there is the possibility for cooperation by just looking at the research themes on the webpages. Sometimes they sound pretty interesting and related but then it turns out that goals are different. It also happens that there are possibilities for cooperation where you do not expect them (which happened to me here in Braunschweig). Hence, I am quite careful here.
  • What lecture did you teach, what would you like to teach and hoe does that fit in our system? While the first two parts are easy, I usually found it quite hard to figure out how some system work from the inspection of the webpages, Modulshandbüchern or Studienordnungen. However, I try to be prepared by looking for lecture in their system which I could give. Often you will be asked “What do you think about “service teaching?” (meaning something like “math for engineers”, “math for biology”,…). There is an obvious false answer here I don’t really know what is the sense of this question…
  • What is your experience with administration? Basically the same as for the “service teaching”-question. There is an obviously false answer.

    For sure there are more standard question and probably I’ll add them as they come to my mind.

    When the committee is through with their questions, you’ll will be asked it you have any. Have some! Ask about the library, the expected travel budget, if there are positions associated to the professorship, the IT administration, how many students are there, if there are plans for larger research projects,…

    Finally, I briefly summarize what happens after the interview: After all job interviews are through, the committee will decide on a subset of the invited guys (I think three to five) and ask some “big shots” in the field for reports. and an the basis of this the committee will form a list (in most cases with three places, exceptionally a shorter list on two or even one, in rare cases with two people on the third place). This takes at least three weeks but can take up to several month. The list has to go through the university administration which may take another few weeks. Strictly speaking you’ll not be contacted unless you are on the first place. However, you can ask the head of the committee (by phone – I not sure if email is appropriate) what has happened to your application. In case you are not on the list, the first thing you’ll hear officially is that the position has be filled (which can be several month or even more that a year later).

  • Today I’d like to blog about two papers which appeared on the arxiv.

    1. Regularization with the Augmented Lagrangian Method – Convergence Rates from Variational Inequalities

    The first one is the paper “Regularization of Linear Ill-posed Problems by the Augmented Lagrangian Method and Variational Inequalities” by Klaus Frick and Markus Grasmair.

    Well, the title basically describes the content quite accurate. However, recall that the Augmented Lagrangian Method (ALM) is a method to calculate solutions to certain convex optimization problems. For a convex, proper and lower-semicontinuous function {J} on a Banach space {X}, a linear and bounded operator {K:X\rightarrow H} from {X} into a Hilbert space {H} and an element {g\in H} consider the problem

    \displaystyle   \inf_{u} J(u)\quad\text{s.t.}\quad Ku=g. \ \ \ \ \ (1)

    The ALM goes as follows: Start with an initial dual variable {p_0}, choose step-sizes {\tau_k>0} and iterate

    \displaystyle  u_k \in \text{argmin}\Big(\frac{\tau_k}{2}\|Ku-g\|^2 + J(u) + \langle p_{k-1},Ku-g\rangle\Big)

    \displaystyle  p_k = p_{k-1}+\tau_k(g-Ku_k).

    (These days one should note that this iteration is also known under the name Bregman iteration…). Indeed, it is known that the ALM converges to a solution of (1) if there exists one. Klaus and Markus consider the ill-posed case, i.e. the range of {K} is not closed and {g} is replaced by some {g^\delta} which fulfills {\|g-g^\delta\|\leq\delta} (and hence, {g^\delta} is generally not in the range of {K}). Then, the ALM does not converge but diverges. However, one observes “semi-convergence” in practice, i.e. the iterates approach an approximate “solution to {Ku=g^\delta}” (or even a true solution to {Ku=g}) first but then start to diverge from some point on. Then it is natural to ask, if the ALM with {g} replaced by {g^\delta} can be used for regularization, i.e. can one choose a stopping index {k^*} (depending on {\delta} and {g^\delta}) such that the iterates {u_{k^*}^\delta} approach the solution of (1) if {\delta} vanishes? The question has been answered in the affirmative in previous work by Klaus (here and here) and also estimates on the error and convergence rates have been derived under an additional assumption on the solution of (1). This assumption used to be what is called “source condition” and says that there should exist some {p^\dag\in H} such that for a solution {u^\dagger} of (1) it holds that

    \displaystyle  K^* p^\dagger \in\partial J(u^\dagger).

    Under this assumption it has been shown that the Bregman distance {D(u_{k^*}^\delta,u^\dag)} goes to zero linearly in {\delta} under appropriate stopping rules. What Klaus and Markus investigate in this paper are different conditions which ensure slower convergence rates than linear. These conditions come in the form of “variational inequalities” which gained some popularity lately. As usual, these variational inequalities look some kind of messy at first sight. Klaus and Markus use

    \displaystyle  D(u,u^\dag)\leq J(u) - J(u^\dag) + \Phi(\|Ku-g\|^2)

    for some positive functional {D} with {D(u,u)=0} and some non-negative, strictly increasing and concave function {\Phi}. Under this assumption (and special {D}) they derive convergence rates which again look quite complicated but can be reduced to simpler and more transparent cases which resemble the situation one knows for other regularization methods (like ordinary Tikhonov regularization).

    In the last section Klaus and Markus also treat sparse regularization (i.e. with {J(u) = \|u\|_1}) and derive that a weak condition (like {(K^*K)^\nu p^\dag\in\partial J(u^\dag)} for some {0<\nu<1/2} already imply the stronger one (1) (with a different {p^\dag}). Hence, interestingly, it seems that for sparse regularization one either gets a linear rate or nothing (in this framework).

    2. On necessary conditions for variational regularization

    The second paper is “Necessary conditions for variational regularization schemes” by Nadja Worliczek and myself. I have discussed some parts of this paper alread on this blog here and here. In this paper we tried to formalize the notion of “a variational method” for regularization with the goal to obtain necessary conditions for a variational scheme to be regularizing. As expected, this goal is quite ambitions and we can not claim that we came up with ultimate necessary condition which describe what kind of variational methods are not possible. However, we could first relate the three kinds of variational methods (which I called Tikhonov, Morozov and Ivanov regularization here) and moreover investigated the conditions on the data space a little closer. In recent years it turned out that one should not always use a term like {\|Ku-g^\delta\|^2} to measure the noise or to penalize the deviation from {Ku} to {g^\delta}. For several noise models (like Poisson noise or multiplicative noise) other functionals are better suited. However, these functionals raise several issues: They are often not defined on a linear space but on a convex set, sometimes with the nasty property that their interior is empty. They often do not have convenient algebraic properties (e.g. scaling invariance, triangle inequalities or the like). Finally they are not necessarily (lower semi-)continuous with respect to the usual topologies. Hence, we approached the data space from quite abstract way: The data space {(Y,\tau_Y)} is topological space which comes with an additional sequential convergence structure {\mathcal{S}} (see e.g. here) and on (a subset of) which there is a discrepancy functional {\rho:Y\times Y\rightarrow [0,\infty]}. Then we analyzed the interplay of these three things {\tau_Y}, {\mathcal{S}} and {\rho}. If you wonder why we use the additional sequential convergence structure, remember that in the (by now classical) setting for Tikhonov regularization in Banach spaces with a functional like

    \displaystyle  \|Ku-g^\delta\|_Y^q + \alpha\|u\|_X^p

    with some Banach space norms {\|\cdot\|_Y} and {\|\cdot\|_X} there are also two kinds of convergence on {Y}: The weak convergence (which is replaced by {\tau_Y} in our setting) which is, e.g., used to describe convenient (lower semi-)continuity properties of {K} and the norm {\|\cdot\|_Y} and the norm convergence which is used to describe that {g^\delta\rightarrow g^\dag} for {\delta\rightarrow 0}. And since we do not have a normed space {Y} in our setting and one does not use any topological properties of the norm convergence in all the proofs of regularizing properties, Nadja suggested to use a sequential convergence structure instead.

    Today I would like to comment on two arxiv-preprints I stumbled upon:

    1. “Augmented L1 and Nuclear-Norm Models with a Globally Linearly Convergent Algorithm” – The Elastic Net rediscovered

    The paper “Augmented L1 and Nuclear-Norm Models with a Globally Linearly Convergent Algorithm” by Ming-Jun Lai and Wotao Yin is another contribution to a field which is (or was?) probably the fastest growing field in applied mathematics: Algorithms for convex problems with non-smooth {\ell^1}-like terms. The “mother problem” here is as follows: Consider a matrix {A\in{\mathbb R}^{m\times n}}, {b\in{\mathbb R}^m} try to find a solution of

    \displaystyle  \min_{x\in{\mathbb R}^n}\|x\|_1\quad\text{s.t.}\quad Ax=b

    or, for {\sigma>0}

    \displaystyle  \min_{x\in{\mathbb R}^n}\|x\|_1\quad\text{s.t.}\quad \|Ax-b\|\leq\sigma

    which appeared here on this blog previously. Although this is a convex problem and even has a reformulation as linear program, some instances of this problem are notoriously hard to solve and gained a lot of attention (because their applicability in sparse recovery and compressed sensing). Very roughly speaking, a part of its hardness comes from the fact that the problem is neither smooth nor strictly convex.

    The contribution of Lai and Yin is that they analyze a slight perturbation of the problem which makes its solution much easier: They add another term in the objective; for {\alpha>0} they consider

    \displaystyle  \min_{x\in{\mathbb R}^n}\|x\|_1 + \frac{1}{2\alpha}\|x\|_2^2\quad\text{s.t.}\quad Ax=b

    or

    \displaystyle  \min_{x\in{\mathbb R}^n}\|x\|_1 + \frac{1}{2\alpha}\|x\|_2^2\quad\text{s.t.}\quad \|Ax-b\|\leq\sigma.

    This perturbation does not make the problem smooth but renders it strongly convex (which usually makes the dual more smooth). It turns out that this perturbation makes life with this problem (and related ones) much easier – recovery guarantees still exists and algorithms behave better.

    I think it is important to note that the “augmentation” of the {\ell^1} objective with an additional squared {\ell^2}-term goes back to Zou and Hastie from the statistics community. There, the motivation was as follows: They observed that the pure {\ell^1} objective tends to “overpromote” sparsity in the sense that if there are two columns in {A} which are almost equally good in explaining some component of {b} then only one of them is used. The “augmented problem”, however, tends to use both of them. They coined the method as “elastic net” (for reasons which I never really got).

    I also worked on elastic-net problems for problems in the form

    \displaystyle  \min_x \frac{1}{2}\|Ax-b\|^2 + \alpha\|x\|_1 + \frac{\beta}{2}\|x\|_2^2

    in this paper (doi-link). Here it also turns out that the problem gets much easier algorithmically. I found it very convenient to rewrite the elastic-net problem as

    \displaystyle  \min_x \frac{1}{2}\|\begin{bmatrix}A\\ \sqrt{\beta} I\end{bmatrix}x-\begin{bmatrix}b\\ 0\end{bmatrix}\|^2 + \alpha\|x\|_1

    which turns the elastic-net problem into just another {\ell^1}-penalized problem with a special matrix and right hand side. Quite convenient for analysis and also somehow algorithmically.

    2. Towards a Mathematical Theory of Super-Resolution

    The second preprint is “Towards a Mathematical Theory of Super-Resolution” by Emmanuel Candes and Carlos Fernandez-Granda.

    The idea of super-resolution seems to pretty old and, very roughly speaking, is to extract a higher resolution of a measured quantity (e.g. an image) than the measured data allows. Of course, in this formulation this is impossible. But often one can gain something by additional knowledge of the image. Basically, this also is the idea behind compressed sensing and hence, it does not come as a surprise that the results in compressed sensing are used to try to explain when super-resolution is possible.

    The paper by Candes and Fernandez-Granada seems to be pretty close in spirit to Exact Reconstruction using Support Pursuit on which I blogged earlier. They model the sparse signal as a Radon measure, especially as a sum of Diracs. However, different from the support-pursuit-paper they use complex exponentials (in contrast to real polynomials). Their reconstruction method is basically the same as support pursuit: The try to solve

    \displaystyle   \min_{x\in\mathcal{M}} \|x\|\quad\text{s.t.}\quad Fx=y, \ \ \ \ \ (1)

    i.e. they minimize over the set of Radon measures {\mathcal{M}} under the constraint that certain measurements {Fx\in{\mathbb R}^n} result in certain given values {y}. Moreover, they make a thorough analysis of what is “reconstructable” by their ansatz and obtain a lower bound on the distance of two Diracs (in other words, a lower bound in the Prokhorov distance). I have to admit that I do not share one of their claims from the abstract: “We show that one can super-resolve these point sources with infinite precision—i.e. recover the exact locations and amplitudes—by solving a simple convex program.” My point is that I can not see to what extend the problem (1) is a simple one. Well, it is convex, but it does not seem to be simple.

    I want to add that the idea of “continuous sparse modelling” in the space of signed measures is very appealing to me and appeared first in Inverse problems in spaces of measures by Kristian Bredies and Hanna Pikkarainen.

    Follow

    Get every new post delivered to your Inbox.

    Join 46 other followers