Aufgabe 1 - Warm Up

Angenommen, eine \(3 \times 3\) Matrix \(C\) habe die Eigenwerte \(0, 1, 2\).
Berechnen Sie, falls möglich (oder argumentieren Sie, warum die Berechnung nicht möglich ist):

Den Rang von \(C\).
Die Determinante von \(C^T C\).
Die Eigenwerte von \(C^T C\).
Die Eigenwerte von \((C^2 + I)^{-1}\).

Aufgabe 2 - Konstruktion von symmetrischen Matrizen (und Quadriken) nach Spektrum

Ziel dieser Aufgabe ist es, zu verstehen, wie wir symmetrische Matrizen mit vorgegebenem Spektrum und Eigenvektoren direkt konstruieren können. Dies ist ungemein nützlich für die verschiedensten Anwendungen, wie z.B. richtungsabhängige Gewichte in Least-Squares-Verfahren, oder zur Konstruktion anisotroper Filter und Basisfunktionen (beides wird in der Vorlesung besprochen).
Häufig besteht der Trick darin, das Spektrum einer Matrix gezielt zu konstruieren. Hier schauen wir uns einige Ansätze dazu an, um Matrizen nach Vorgaben über ihr Spektrum zu konstruieren.

Es sei \(u \in \mathbb{R}^d, ||u||>0\).
Zeigen Sie, dass \(u\) ein Eigenvektor der Matrix \(uu^T\) ist, mit Eigenwert \(||u||^2\).
Zeigen Sie, dass die Matrix \(uu^T\) nur einen einzigen Eigenvektor hat, der nicht Null ist.
Sei nun \(u \in \mathbb{R}^d, ||u|| = 1\).
Zeigen Sie, dass \(I - uu^T\) nur einen Eigenwert \(0\) besitzt, alle weiteren Eigenwerte sind \(1\).
(Zum Eigenwert \(0\) gehören die Eigenvektoren \(c \cdot u,\, c \in \mathbb{R}^{\neq 0}\), aber das muss hier nicht bewiesen werden)

Tipp: Was sind die Eigenwerte der Identitätsmatrix \(I\)?
Konstruieren Sie eine symmetrische Matrix \(M\) mit den Eigenwerten \(\lambda_1, \dots, \lambda_d\) und orthogonales Eigenvektoren \(u_1, \dots, u_n\) (beides ist gegeben, daraus soll die Matrix gebaut werden).
Zeigen Sie kurz, dass Ihre Konstruktion korrekt ist.
Gegeben sei eine symmetrische Matrix \(M \in \mathbb{R}^{d \times d}\) (z.B. aus gemessenen Daten konstruiert).
Benutzen Sie die SVD um diese Matrix als Linearkombination von Matrizen vom Rank \(1\) dazustellen.
Kann dies auch für nicht symmetrische Matrizen funktionieren? (Tipp: Ja! Aber warum?)
Hinweis: Das ist recht einfach; die eigentlich Aufgabe besteht darin, den Zusammenhang zu erkennen.

Aufgabe 3 - Inverse Probleme

Dieses Mal lösen wir unser erstes "richtiges" Problem!

Wir rekonstruieren (mit einem zugegebenermaßen recht einfachen Ansatz) ein Modell zu gegebenen verrauschen Messdaten. Als Beispiel schauen wir uns den Klassiker der inversen Probleme an - die Rekonstruktion von tomographischen Daten mittels regularisierter Inversion der Radontransformation (effizientere Varianten dieser Methode werden tatsächlich in der der Praxis oft benutzt, insbesondere für tomographische Verfahren in der Medizin wie z.B. CT/MRI/PET etc.).

Erläuterung: Wie funktioniert ein Computertomographiescanner (CT)? Das Gerät macht sehr viele Röntgenbilder eines Patienten, wobei sich der Scanner (also Röntgenquelle und Photodetektor) um den Patienten dreht. In jeder Schicht senkrecht zur Drehachse ergibt sich eine Situation ähnlich wie in Abbildung 1: Jeder Pixel im Röntgenbild misst die integrale Absorption entlang einer Linie (hier als parallel angenommen, zur Vereinfachung). Durch Bilden des Logarithmus, erhält man die Summen der logarithmierten Absorptionsdichten. Diese Transformation - von einer Dichtefunktion zu ihren Linienintegralen entlang aller möglichen Graden nennt man auch Radontransformation. Dies ist eine lineare Abbildung; ihr Inverses ist die inverse Radontransformation (Wer hätte das gedacht?), und die erlaubt uns, aus einem CT Scan Datensatz, die Dichte im Patienten zu rekonstruieren.

Aufgabe 3.1 - Die Radontransformation

Vollziehen Sie noch einmal die Erklärung zur Radontransformation aus der Vorlesung genau nach, und überlegen Sie sich, wie man diese (für Pixelbilder) mit Hilfe von numerischer Integration diskretisieren kann.
Implementieren Sie eine 2D Radontransformation.
Laden Sie ein Bild ihrer Wahl ein (Graustufen reichen), berechnen Sie dessen Radontransformation und visualisieren Sie diese. Das Prinzip der Transformation ist in Abbildung 1 dargestellt.
Bestimmen Sie als erstes die Matrix, die die Radontransformation (Abbildung von Pixeln auf die Werte der Linienintegrale) darstellt.
Wir benötigen diese Matrix für den nächsten Aufgabenteil.

Aufgabe 3.2 - Die Inverse Radontransformation

Untersuchen Sie die Eigenschaften der Transformation indem Sie sich die SVD der Transformationsmatrix ansehen.
Insbesondere ist es sehr aufschlussreich, sich das Singulärwertspektrum anzusehen.
Man stellt fest, dass die Radontransformation schlecht gestellt („ill-posed“) ist - die Spreizung der Singulärwerte ist relativ stark, was eine naive Invertierung schwierig macht (unmöglich mit echten, verrauschten Messdaten). Historisch ist dies eines der Probleme, die zur Entwicklung der Theorie schlecht gestellter Probleme geführt hat.
Plotten Sie dazu das Spektrum – z.B. mit Matplotlib.
Visualisieren Sie den Kern der Radontransformation:
Zeigen Sie einige Beispiel von Eingabebildern, die fast vollständig auf null abgebildet werden.
Im Gegenzug, finden Sie Eingabebilder die kaum durch die Transformation abgeschwächt werden.
Hinweis: Schauen Sie sich die Singulärvektoren (auf der richtigen Seite der Matrix) an.
Berechnen Sie nun die inverse Radontransformation mit Hilfe einer (entsprechend angepassten) Pseudoinversen (also eine SVD-basierte Matrixinversion bei der kleine Singulärwerte passend abgeschnitten werden).
Wenden Sie diese auf verschiedene Eingabebilder an, bei denen unterschiedlich viel Rauschen künstlich hinzugefügt wurde (um einen realen Messprozess zu simulieren).

Anmerkungen: Die Invertierung via SVD ist sehr teuer (in der Praxis wird das daher auch in der Regel anders implementiert, mittels schneller Fouriertransformation o.ä.). Bildgrößen von ca. \(64^2\) Pixel ließen sich in meinen Experimenten noch mit halbwegs vertretbarem Aufwand invertieren.