Kap. 9: Singulärwertzerlegung

9.1Kochrezept der Singulärwertzerlegung

9.1.1 Was ist eine Singulärwertzerlegung?

Stell dir vor, jede Matrix wäre nichts weiter als ein Hintereinander von drehen, dann strecken, dann nochmal drehen. Genau das sagt die Singulärwertzerlegung (kurz SVD, von englisch singular value decomposition): Wir schreiben eine beliebige Matrix $A$ als Produkt von drei besonders einfachen Bausteinen $U$ , $S$ und $V$ .

Wenn $A$ einen Vektor $\mathbf{x}$ transformiert, lässt sich das in drei Etappen lesen: erst dreht $V^{\mathsf{T}}$ den Vektor in ein neues Koordinatensystem, dann staucht oder streckt $S$ die einzelnen Achsen, und zum Schluss dreht $U$ das Ergebnis wieder zurück in den Zielraum. Die Streckfaktoren auf der Diagonalen von $S$ heißen Singulärwerte, und sie sind der eigentliche Kern dieses Kapitels.

Ein anschauliches Bild dazu: nimm den Einheitskreis (alle Vektoren der Länge 1) und schau, wohin $A$ ihn schickt. Heraus kommt immer eine Ellipse. Die Längen ihrer Halbachsen sind genau die Singulärwerte $\sigma_1, \sigma_2, \ldots$ Die SVD zerlegt die Wirkung von $A$ also in „in welche Richtungen wird wie stark gestreckt“, und das ist eine der nützlichsten Sichtweisen der ganzen linearen Algebra.

!!!

Singulärwertzerlegung einer Matrix

A = U\,S\,V^{\mathsf{T}}

Jede Matrix A lässt sich so zerlegen: Drehung, Streckung, Drehung.

Dimensionen der drei Faktoren

U \in \mathbb{R}^{m\times m}, \qquad S \in \mathbb{R}^{m\times n}, \qquad V \in \mathbb{R}^{n\times n}

U und V sind quadratisch, S hat dieselbe m×n-Gestalt wie A.

Zwei Eigenschaften machen diese Bausteine so brauchbar. Erstens sind $U$ und $V$ orthogonal. Das heißt: ihre Spalten stehen paarweise senkrecht aufeinander und haben alle die Länge 1 (man nennt das orthonormiert). Eine orthogonale Matrix dreht und spiegelt nur, sie verzerrt nichts und ändert keine Längen. In Formeln ausgedrückt gilt $U^{\mathsf{T}}U = I$ und $V^{\mathsf{T}}V = I$ , wobei $I$ die Einheitsmatrix ist.

Zweitens ist $S$ eine Diagonalmatrix: außerhalb der Hauptdiagonalen stehen nur Nullen, und auf der Diagonalen sitzen die Singulärwerte. Genau diese Diagonalgestalt macht die mittlere Etappe zu einer reinen Streckung Achse für Achse. Achtung: $S$ ist nur dann quadratisch, wenn $A$ quadratisch ist. Bei einer nicht-quadratischen Matrix ( $m \neq n$ ) erbt $S$ deren Rechteckform $m \times n$ und bekommt zusätzlich Nullzeilen oder Nullspalten (mehr dazu im Kochrezept).

Definition Singulärwertzerlegung
Zerlegung

A = U\,S\,V^{\mathsf{T}}

einer beliebigen Matrix

A \in \mathbb{R}^{m\times n}

in zwei orthogonale Matrizen

U

V

und eine Diagonalmatrix

S

. Geometrisch: Drehung, dann Streckung, dann Drehung.

Notation Notation: $A^{\mathsf{T}}$
Gesprochen „

A

transponiert“: die an der Hauptdiagonalen gespiegelte Matrix (Zeilen werden Spalten). Manche Texte schreiben

A^t

oder

A'

; wir schreiben durchgehend

A^{\mathsf{T}}

Notation Notation: orthogonale Matrix
Matrix, deren Spalten paarweise senkrecht und auf Länge 1 normiert sind. Es gilt

U^{\mathsf{T}}U = I

, also

U^{-1} = U^{\mathsf{T}}

. Sie dreht und spiegelt nur, ändert keine Längen.

Notation Notation: Diagonalmatrix $S$
Matrix mit den Singulärwerten

\sigma_1, \sigma_2, \ldots

auf der Hauptdiagonalen und sonst nur Nullen.

S

hat dieselbe Form

m\times n

wie

A

Querverweis Verweise
→ Kap. 6 Eigenwertproblem

9.1.2 Kochrezept der Singulärwertzerlegung

Schön und gut, $A = U S V^{\mathsf{T}}$ . Aber wie kommt man bei einer konkreten Matrix an die drei Faktoren? Die gute Nachricht: es gibt ein festes Rezept mit sechs Schritten, und alles baut auf einer einzigen Hilfsmatrix auf, nämlich $A^{\mathsf{T}}A$ .

Warum gerade $A^{\mathsf{T}}A$ ? Diese Matrix ist quadratisch und symmetrisch, ganz egal wie $A$ aussah. Und symmetrische Matrizen können wir laut Kapitel 6 immer reell diagonalisieren, also ihre Eigenwerte und eine orthonormierte Basis aus Eigenvektoren finden. Genau diese beiden Zutaten brauchen wir. Die Singulärwerte sind die Wurzeln der Eigenwerte von $A^{\mathsf{T}}A$ , und die Eigenvektoren liefern die Spalten von $V$ . Folge dem Rezept einfach Schritt für Schritt.

Kochrezept in 6 Schritten

Schritt 1: Eigenwerte und Eigenvektoren von $A^{\mathsf{T}}A$ bestimmen

$A^{\mathsf{T}}A$ ist quadratisch und symmetrisch, also reell diagonalisierbar (Kapitel 6). Darum dieser Umweg: über diese Hilfsmatrix bekommen wir alles, was wir brauchen.

Bilde $A^{\mathsf{T}}A \in \mathbb{R}^{n\times n}$ und berechne ihre Eigenwerte. Ordne sie absteigend; die ersten $r$ sind positiv, der Rest ist null:

$\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_r > \lambda_{r+1} = \dots = \lambda_n = 0$
Schritt 2: Orthonormalbasis aus den Eigenvektoren bilden ( $\to V$ )

$V$ muss orthogonal sein, deshalb brauchen wir die Eigenvektoren orthonormiert (mit Gram-Schmidt, falls sie es nicht schon sind).

Schreibe die orthonormierten Eigenvektoren $\mathbf{v}_1, \ldots, \mathbf{v}_n$ als Spalten in eine Matrix:

$V = (\mathbf{v}_1 \;\cdots\; \mathbf{v}_n) \in \mathbb{R}^{n\times n}$
Schritt 3: Singulärwerte ausrechnen und $S$ aufbauen

Die Streckfaktoren der Abbildung stecken in den Eigenwerten von $A^{\mathsf{T}}A$ ; die Wurzel daraus ergibt die Singulärwerte.

Die Singulärwerte sind die Wurzeln der Eigenwerte, für $i = 1, \ldots, \min\{m, n\}$ :

$\sigma_i = \sqrt{\lambda_i}$
Schritt 3 (Forts.): Gestalt von $S$ je nach Form von $A$

$S$ erbt die Form $m\times n$ von $A$ . Ist $A$ breiter als hoch ( $m < n$ ), bekommt $S$ Nullspalten rechts; ist $A$ höher als breit ( $m > n$ ), bekommt $S$ Nullzeilen unten.

Fall $m < n$ (breit, Nullspalten rechts) und Fall $m > n$ (hoch, Nullzeilen unten):

$\begin{aligned} S &= \begin{pmatrix} \sigma_1 & & & 0 & \cdots & 0 \\ & \ddots & & \vdots & & \vdots \\ & & \sigma_m & 0 & \cdots & 0 \end{pmatrix} \quad (m<n), \\[8pt] S &= \begin{pmatrix} \sigma_1 & & \\ & \ddots & \\ & & \sigma_n \\ 0 & \cdots & 0 \\ \vdots & & \vdots \\ 0 & \cdots & 0 \end{pmatrix} \quad (m>n) \end{aligned}$
Schritt 4: Linke Singulärvektoren $\mathbf{u}_i$ berechnen

Aus den $\mathbf{v}_i$ und den Singulärwerten ergeben sich die ersten $r$ Spalten von $U$ . Definiert ist das nur für $\sigma_i \neq 0$ , also für $i = 1, \ldots, r$ .

Für jeden positiven Singulärwert:

$\mathbf{u}_i = \frac{1}{\sigma_i}\,A\,\mathbf{v}_i \qquad (i = 1, \ldots, r)$
Schritt 5: $U$ zu einer Orthonormalbasis ergänzen, falls $r < m$

$U$ muss quadratisch und orthogonal sein. Liefert Schritt 4 weniger Spalten als $m$ , fehlen also welche, fülle sie zu einer Orthonormalbasis (ONB) auf.

Ergänze $\mathbf{u}_1, \ldots, \mathbf{u}_r$ zu einer vollständigen ONB, sodass:

$U = (\mathbf{u}_1 \;\cdots\; \mathbf{u}_m) \in \mathbb{R}^{m\times m}$
Schritt 6: Endresultat zusammensetzen

Jetzt sind alle drei Faktoren da. Mehr ist nicht zu tun.

Schreibe das Ergebnis einfach hin:

$A = U\,S\,V^{\mathsf{T}}$

Formel Schlüsselformel

\sigma_i = \sqrt{\lambda_i}

Die Singulärwerte von

A

sind die Wurzeln der Eigenwerte von

A^{\mathsf{T}}A

. Genau diese Brücke verbindet die SVD mit dem Eigenwertproblem aus Kapitel 6.

Formel Linke Singulärvektoren

\mathbf{u}_i = \frac{1}{\sigma_i}\,A\,\mathbf{v}_i

Spalten von

U

, nur für

\sigma_i \neq 0

definiert.

Definition Singulärwert
Streckfaktor der Abbildung

A

, also die Länge einer Halbachse der Bild-Ellipse. Definiert als

\sigma_i = \sqrt{\lambda_i}

mit den Eigenwerten

\lambda_i

von

A^{\mathsf{T}}A

Notation Notation: $r$
Anzahl der von null verschiedenen (positiven) Singulärwerte. Das ist zugleich der Rang von

A

. In der Vorlesung nicht eigens benannt; diese Lesart ist unsere Anschauungshilfe.

Prüfungstipp Reihenfolge merken: immer

\sigma_1 \ge \sigma_2 \ge \ldots \ge \sigma_r > 0

Querverweis Verweise
→ Kap. 6 Eigenwertproblem

9.1.3 Beispiel: SVD einer 2×2-Diagonalmatrix

Genug Theorie, wir laufen das Rezept einmal an der einfachsten denkbaren Matrix durch: einer $2 \times 2$ -Diagonalmatrix. Gesucht ist ihre vollständige Singulärwertzerlegung $M = U S V^{\mathsf{T}}$ .

SVD von $M = \mathrm{diag}(2, \tfrac12)$

Gegeben

Die Ausgangsmatrix:

$M = \begin{pmatrix} 2 & 0 \\ 0 & \tfrac12 \end{pmatrix}$
Schritt 1: $M^{\mathsf{T}}M$ berechnen

Erster Schritt des Rezepts: die symmetrische Hilfsmatrix bilden.

Da $M$ diagonal ist, ist $M^{\mathsf{T}} = M$ , und das Produkt quadriert einfach die Diagonaleinträge:

$M^{\mathsf{T}}M = \begin{pmatrix} 4 & 0 \\ 0 & \tfrac14 \end{pmatrix}$
Schritt 2: Eigenwerte ablesen

$M^{\mathsf{T}}M$ ist diagonal, deshalb sind die Eigenwerte direkt die Diagonaleinträge, nichts zu rechnen.

Geordnet ( $\lambda_1 \ge \lambda_2$ ):

$\lambda_1 = 4, \qquad \lambda_2 = \tfrac14$
Schritt 3: Singulärwerte

Singulärwerte sind die Wurzeln der Eigenwerte.

Also:

$\sigma_1 = \sqrt{4} = 2, \qquad \sigma_2 = \sqrt{\tfrac14} = \tfrac12$
Schritt 4: Eigenvektoren $\mathbf{v}_i$

Die Eigenvektoren einer Diagonalmatrix sind die Standard-Einheitsvektoren, schon orthonormiert.

Damit ist $V$ die Einheitsmatrix:

$\mathbf{v}_1 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \qquad \mathbf{v}_2 = \begin{pmatrix} 0 \\ 1 \end{pmatrix}$
Schritt 5: linke Singulärvektoren $\mathbf{u}_i$ berechnen

Mit $\mathbf{u}_i = \tfrac{1}{\sigma_i} M \mathbf{v}_i$ ergeben sich die Spalten von $U$ .

Für $\mathbf{u}_1$ (Faktor $\tfrac{1}{\sigma_1} = \tfrac12$ ) und $\mathbf{u}_2$ (Faktor $\tfrac{1}{\sigma_2} = 2$ ):

$\begin{aligned} \mathbf{u}_1 &= \frac{1}{\sigma_1}\,M\,\mathbf{v}_1 = \frac12 \begin{pmatrix} 2 & 0 \\ 0 & \tfrac12 \end{pmatrix}\begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix} \\[4pt] \mathbf{u}_2 &= \frac{1}{\sigma_2}\,M\,\mathbf{v}_2 = \frac{1}{1/2} \begin{pmatrix} 2 & 0 \\ 0 & \tfrac12 \end{pmatrix}\begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \end{pmatrix} \end{aligned}$
Resultat

Alle drei Faktoren stehen. $S$ trägt die Singulärwerte, $U$ und $V$ sind hier beide die Einheitsmatrix.

Die vollständige Zerlegung lautet:

$\begin{aligned} S &= \begin{pmatrix} 2 & 0 \\ 0 & \tfrac12 \end{pmatrix}, \\[4pt] V = V^{\mathsf{T}} &= \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \\[4pt] U &= \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \end{aligned}$

Merke Merke
Bei einer Diagonalmatrix lassen sich die Eigenwerte direkt von der Diagonalen ablesen; man muss kein charakteristisches Polynom lösen.

Querverweis Verweise
→ 9.1.2 Kochrezept

9.1.4 Beispiel: nur die Singulärwerte einer 3×2-Matrix

Manchmal will man gar nicht die ganze Zerlegung, sondern nur die Singulärwerte selbst, etwa um die Kondition oder die Norm einer Matrix abzuschätzen. Dann hört man nach Schritt 3 einfach auf, sobald $S$ steht. Dieses Beispiel zeigt das und gleichzeitig den Fall $m > n$ , bei dem $S$ eine Nullzeile bekommt.

Die Matrix $A$ ist $3 \times 2$ , also höher als breit ( $m = 3 > n = 2$ ). Die Hilfsmatrix $A^{\mathsf{T}}A$ ist trotzdem nur $2 \times 2$ , denn ihre Größe richtet sich nach der Spaltenzahl $n$ , nicht nach $m$ .

Singulärwerte von $A \in \mathbb{R}^{3\times 2}$

Gegeben

Die Ausgangsmatrix (drei Zeilen, zwei Spalten):

$A = \begin{pmatrix} -3 & 0 \\ 0 & 3 \\ \sqrt{3} & 2 \end{pmatrix}$
Schritt 1: $A^{\mathsf{T}}A$ berechnen

Wieder die symmetrische Hilfsmatrix bilden. $A^{\mathsf{T}}$ ist $2\times 3$ , also wird das Produkt $2\times 2$ .

Zeile mal Spalte ausmultiplizieren:

$\begin{aligned} A^{\mathsf{T}}A &= \begin{pmatrix} -3 & 0 & \sqrt{3} \\ 0 & 3 & 2 \end{pmatrix} \begin{pmatrix} -3 & 0 \\ 0 & 3 \\ \sqrt{3} & 2 \end{pmatrix} \\[4pt] &= \begin{pmatrix} 12 & 2\sqrt{3} \\ 2\sqrt{3} & 13 \end{pmatrix} \end{aligned}$
Schritt 2: Eigenwerte bestimmen

Bei einer $2\times 2$ -Matrix über das charakteristische Polynom $\det(A^{\mathsf{T}}A - \lambda I) = 0$ . Hier liefert das eine quadratische Gleichung in $\lambda$ .

Geordnet ( $\lambda_1 \ge \lambda_2$ ):

$\lambda_1 = 16, \qquad \lambda_2 = 9$
Schritt 3: Singulärwerte

Wurzeln der Eigenwerte ziehen.

Also:

$\sigma_1 = \sqrt{16} = 4, \qquad \sigma_2 = \sqrt{9} = 3$
Schritt 4: $S$ aufbauen (Fall $m > n$ )

Weil $m = 3 > n = 2$ , hat $S$ die Form $3\times 2$ : die Singulärwerte oben auf der Diagonalen, darunter eine Nullzeile (vgl. den Fall $m>n$ aus dem Kochrezept).

Damit sind die Singulärwerte gefunden und $S$ steht:

$S = \begin{pmatrix} 4 & 0 \\ 0 & 3 \\ 0 & 0 \end{pmatrix}$

Notation Notation: $\sqrt{3}$
Wurzelausdrücke bleiben exakt stehen, nicht als Dezimalzahl runden. So bleibt etwa

A^{\mathsf{T}}A

exakt und die Eigenwerte

16

und

9

kommen sauber heraus.

Merke Merke

m > n

S

erbt Nullzeilen unten.

m < n

S

erbt Nullspalten rechts. Die Größe von

A^{\mathsf{T}}A

richtet sich nach

n

, nicht nach

m

Querverweis Verweise
→ 9.1.2 Kochrezept, Schritt 3

Aufgaben mit Musterlösungen

Eigene Übungsaufgaben zur Singulärwertzerlegung folgen. Bis dahin sind die beiden durchgerechneten Beispiele in 9.1.3 und 9.1.4 die beste Vorlage, um das Kochrezept selbst zu üben.

Die Aufgaben für dieses Kapitel werden in einer zukünftigen Version ergänzt.

MerkeErst selbst rechnen, dann Lösung prüfen!