Aufgabe 1 - Quadratische Minimierungsprobleme

Gegeben sei eine Energie-Funktion \(E\), welche ein multivariates Polynom zweiten Grades in den Eingabevariablen ist: \[ E:\mathbb{R}^d \rightarrow \mathbb{R}, \quad E(x) = x^T A x + b x + c. \]

Wie in der Vorlesung nutzen wir hier die Matrixschreibweise, wobei

• \(A \in \mathbb{R}^{d \times d}\) eine symmetrische, reelle Matrix ist, die die quadratischen Koeffizienten enthält,
• \(b \in \mathbb{R}^d , c \in \mathbb{R}\) jeweils den linearen und den konstanten Anteil beschreiben, und
• die Variable \(x=(x_1, \ldots, x_d)\) ein \(d\)-dimensionaler Vektor ist.

Wir betrachten nun den Gradientenvektor von \(E\) nach \(x\): \[ \nabla E := \nabla_x E := \left( \begin{array}{cc} \partial_1 \\ \vdots \\ \partial_d \\ \end{array}\right) E, \] also den Vektor aller partiellen Ableitungen nach \(x_1, \ldots, x_d\).

1. Zeigen Sie, dass \(\nabla_x E = 2 Ax + b\) gilt.
2. Erklären Sie qualitativ (kein formaler Beweis; nur nachzuvollziehen und in der Übung in Worten erklären):
   Falls \(A\) invertierbar ist¹, verschwindet an der Stelle \(x = - \frac{1}{2} A^{-1}b\) der Gradient.
   Dies bedeutet, hier könnte ein lokales Minimum liegen (warum ist das notwendig?); falls \(A\) positiv-definit ist, ist dies auch das globale Minimum (warum?).
3. Entwurf einer konkreten quadratischen Zielfunktion, Teil 1:
   Gegeben sei ein Punkt \(p \in \mathbb{R}^3\). Entwerfen Sie eine quadratische Funktion \(q(x), x \in \mathbb{R}^3\), die als Wert den quadratischen Abstand des Punktes \(x\) zum Punkt \(p\) ausgibt.
   Hinweis: Ja, das ist wirklich einfach...
4. Entwurf einer konkreten quadratischen Zielfunktion, Teil 2:
   Gegeben sei eine Ebene in 3D durch drei nicht kollineare Punkte \(p_1, p_2, p_3 \in \mathbb{R}^3\). Entwerfen Sie eine quadratische Funktion \(q(x), x \in \mathbb{R}^3\), die als Wert den quadratischen Abstand des Punktes \(x\) von der Ebene angibt.
   Hinweis: Hier gibt es natürlich verschiedene Ansätze.
5. Regularisierung von quadratischen Problemen.
   Gegeben sei eine positiv-semidefinite, symmetrische Matrix \(A \in \mathbb{R}^{d \times d}\) (mit Eigenwerten \(\lambda_1, \ldots, \lambda_d \in \mathbb{R}^{\ge0}\)).
   Erklären Sie, warum \(A + \epsilon I\) für \(\epsilon \gt 0\) (ebenfalls) diagonalisierbar ist. Zeigen Sie dann, dass der kleinste Eigenwert dieser neuen Matrix nicht kleiner als \(\epsilon + \min_{i = 1 \ldots d} \lambda_i\) ist.
   Warum können so schlecht konditionierte least-squares-Probleme regularisiert werden?
   Erklären Sie den "praktischen" Nutzen.

Aufgabe 2 - "Can I haz Eigenvalues?"

1. Wir berechnen Eigenkatzen!
   (Ähnlich wie die Eigenfaces von Blanz et al.¹, die in der Vorlesung gezeigt wurden).
   
   Wir bestimmen zunächst die Katzenvektoren des Datensatzes von Blatt 1, indem wir die Punkte jeder Pose dieses Mal einfach "stacken", also in einen langen Vektor in beliebiger, aber fester Ordnung schreiben. Zum Beispiel können wir einen Katzenvektor \(k^{(i)}\) für Katze \(i\) folgendermaßen definieren: \[ k^{(i)} = ( \color{darkred}p_{1,x}^{(i)}, \color{darkred}p_{1,y}^{(i)}, \color{darkred}p_{1,z}^{(i)}, \color{darkred}p_{2,x}^{(i)}, \color{darkred}p_{2,y}^{(i)}, \color{darkred}p_{2,z}^{(i)}, \dots, \color{darkred}p_{n,z}^{(i)} )^T, \] wobei \(p_{j,x}, p_{j,y}, p_{j,z}\) die 3D-Komponente des Punktes mit Index \(j\) (von \(n\)) der Katze mit Index \(i\) (von \(N\)) darstellen.
   
   Insgesamt fassen wir im folgenden den ganzen Datensatz als Datenmatrix zusammen, indem wir die Katzenvektoren in die Spalten der Matrix schreiben: \[ K := \begin{pmatrix}k^{(1)} - μ, & k^{(2)} - μ, & \cdots & k^{(N)} - μ\end{pmatrix} \in \mathbb{R}^{3\cdot n \times N}. \]
   
   Achtung: Die Schreibweise in Spaltenform hat den großen Vorteil, dass sich die restlichen Formeln sehr einfach mit der Vektor-Notation der Vorlesung zusammenbringen lassen. Manchmal sieht man aber auch, dass die Daten in der Datenmatrix zeilenweise notiert werden, etwa in einigen Frameworks.
2. Zuerst schauen wir uns den in der Vorlesung dargestellten Algorithmus nochmals genau an:
   
   1. Wir haben PCA als Lösung des Eigenwertproblems der Scatter (oder Kovarianz-) Matrix \(S(K) := K\cdot K^T\) kennen gelernt.
      Die Hauptachsen des Datensatzes sind die Eigenwert-/vektorpaare dieser Matrix.
      Verifizieren Sie kurz, dass unsere Notation der Kovarianzmatrix mit der aus der Vorlesung (Folie 18, Video 16) übereinstimmt.
   2. Wir können stattdessen auch direkt die Singulärwertzerlegung \(K = UDV^T\) verwenden, um die Hauptkomponentenanalyse zu bestimmen.
      Warum ist das so und wie können wir nun die Hauptachsen ablesen?
   Info: Auf dem nächsten Übungsblatt werden wir noch zwei weitere Möglichkeiten kennen lernen, wie man die PCA alternativ durchführen kann.
3. Wir untersuchen den Datensatz nun mittels PCA: (Wählen Sie gerne eine beliebige der oben beschriebenen Möglichkeiten und nutzen Sie zur Berechnung die entsprechende Numpy Funktion, etwa numpy.linalg.svd für die Singulärwertzerlegung).
   
   Am Beispiel Singulärwertzerlegung:
   Wir berechnet also die Singulärwertzerlegung der Datenmatrix. \[ K = U D V^T = U \left( \begin{array}{cc} \sigma_1 & & \\ & \ddots & \\ & & \sigma_n\\ \end{array}\right) V^T \]
   
   
   1. Erklären Sie warum hier nur die ersten \(8\) Singulärwerte ungleich \(0\) sein sollten.
      
   2. Betrachen Sie nun die linkshändigen ("Ausgabedimension" oder) Singulärvektoren.
      Diese bilden eine neue, \(8\)-dimensionale "Eigenbasis" für den gerade eben gelernten Raum der Katzenposen. Um diese zu verstehen, untersuchen wir die folgenden Morphs. (Wir nehmen implizit an, dass die erhaltenen Eigenvektoren \(u^{(j)}\) mit den Komponenten \(u_1^{(j)}, \dots, u_n^{(j)} \in \mathbb{R}^3\) die Eckpunktkoordinaten, wieder als 3D Punkte aufgefasst werden, d.h. wir "unstacken" den Vektor genauso, wie wir ihn ursprünglich zusammengesetzt hatten; der erste Eintrag liefert die x-Koordiante von Punkt 1, dann die y-Koordinate, usw.).
      
      Ähnlich zu Blatt 1 bestimmen wir die folgenden Morphs des Katzenraums \(m_1, \dots, m_n \in \mathbb{R}^3\): \[ m_i = \mu_i + \sum_{j=1}^8 \lambda_j \cdot \sigma_j \cdot u_i^{(j)}. \] Die Koordinaten \(\lambda_1, \dots , \lambda_8 \in \mathbb{R}\) manövrieren uns durch den Katzenhyperspace (wobei wir die Basisvektoren auch mit den Singulärwerten skalieren). Sinnvolle Werte für diese Koordianten liegen ca. im Bereich \(-2\) bis \(+2\). Größere Beträge liefern Verzerrungen, analog zu Blatt 1.
      
      
      • Visualisieren Sie die Morphs. Wenn man es richtig programmiert, ist der Effekt recht verblüffend!
      • Welche Effekte werden durch die Singulärvektorbasis erfasst?
      • Wo ist der Unterschied zur einfachen Affinen Interpolation der Ausgangsposen aus Blatt 1?

[1] Blanz, Volker, and Thomas Vetter. "A morphable model for the synthesis of 3D faces." Proceedings of the 26th annual conference on Computer graphics and interactive techniques. ACM Press/Addison-Wesley Publishing Co., 1999.