Singulärwertzerlegung

Singulärwertzerlegung am Beispiel einer zweidimensionalen, reellen Scherung $M$: Diese Transformation verzerrt den blauen Einheitskreis oben links zur Ellipse rechts oben im Bild. $M$ kann zerlegt werden in zwei Drehungen $U$ und $V^{*}$ sowie eine Dehnung/Stauchung $\Sigma$ entlang der Koordinatenachsen. Die Singulärwerte $\sigma _{1}$ und $\sigma _{2}$ sind die Längen der großen bzw. kleinen Halbachse der Ellipse. Die genauen Werte für dieses Beispiel finden sich in der Bildbeschreibung.

Eine Singulärwertzerlegung (engl. Singular Value Decomposition; abgekürzt SWZ oder SVD) einer Matrix bezeichnet deren Darstellung als Produkt dreier spezieller Matrizen. Daraus kann man die Singulärwerte der Matrix ablesen. Diese charakterisieren, ähnlich den Eigenwerten, Eigenschaften der Matrix. Singulärwertzerlegungen existieren für jede Matrix – auch für nichtquadratische Matrizen.

Definition

Als Singulärwertzerlegung einer komplexen $m\times n$-Matrix $M$ mit Rang $r$ bezeichnet man ein Produkt der Gestalt

$M=U\Sigma V^{*},$

wobei

• $U$ eine unitäre $m\times m$-Matrix ist,
• $V^{*}$ eine unitäre $n\times n$-Matrix und
• $\Sigma$ eine reelle $m\times n$-Matrix der Gestalt

$\Sigma =\left({\begin{array}{ccc|ccc}\sigma _{1}&&&&\vdots &\\&\ddots &&\cdots &0&\cdots \\&&\sigma _{r}&&\vdots &\\\hline &\vdots &&&\vdots &\\\cdots &0&\cdots &\cdots &0&\cdots \\&\vdots &&&\vdots &\\\end{array}}\right)$

mit $\sigma _{1}\geq \dotsb \geq \sigma _{r}>0$ ist.

Die positiven Diagonaleinträge $\sigma _{i},i=1,\dotsc ,r$ von $\Sigma$ heißen Singulärwerte von $M$. Die Singulärwerte und damit auch die Matrix $\Sigma$ sind durch $M$ bis auf Reihenfolge eindeutig bestimmt. Die Spaltenvektoren $u_{i},i=1,\dotsc ,m$ von $U$ heißen Links-Singulärvektoren, die Spaltenvektoren $v_{i},i=1,\dotsc ,n$ von $V$ heißen Rechts-Singulärvektoren (zum Index $i$) der Matrix $M$. Weder $U$ noch $V$ sind eindeutig bestimmt.

Eigenschaften

Jede Matrix besitzt mindestens eine Singulärwertzerlegung. Bei einer reellen Matrix können die Matrizen $U$ und $V$ der Zerlegung reell gewählt werden.

Wegen

$M^{*}\cdot M=\left(V\Sigma ^{T}U^{*}\right)\cdot \left(U\Sigma V^{*}\right)=V\Sigma ^{T}\Sigma V^{*}$

ist $M^{*}M$ ähnlich zu $\Sigma ^{T}\Sigma$. Damit sind die Singulärwerte der Matrix $M$ gleich den Quadratwurzeln aus den positiven Eigenwerten von $M^{*}M$. Daher ist die Spektralnorm von $M$ gleich dem größten Singulärwert $\sigma _{1}$, $\left\|M\right\|_{2}=\sigma _{1}$. Weiterhin ist die Frobeniusnorm die euklidische Norm des Vektors der Singulärwerte, $\left\|M\right\|_{F}=\left\|[\sigma _{i}]_{i=1}^{r}\right\|_{2}$.

Einsetzen und Nachrechnen zeigt, dass sich die Pseudoinverse (bei Invertierbarkeit die Inverse) zu $M$ aus

$M^{+}=V\Sigma ^{+}U^{*}$

mit

$(\Sigma ^{+})_{ij}={\begin{cases}{\frac {1}{\sigma _{i}}},&{\text{falls}}\ i=j\leq r,\\0&{\text{sonst}}\end{cases}}$

ergibt. Somit sind die Singulärwerte der Inversen zu $M$ genau ${\tfrac {1}{\sigma _{i}}}$, und die auf die Spektralnorm bezogene Konditionszahl von $M$ ergibt sich zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \kappa_2(M)=\tfrac{\sigma_1}{\sigma_n}} .

Da unitäre Transformationen den Betrag der Determinante nicht ändern, gilt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left|\det(M)\right|=\prod_{i=1}^r \sigma_i,}

falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} eine quadratische Matrix mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \det(M) \neq 0} ist.

Es gilt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M v_i = \sigma_i u_i}

und

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M^T u_i = \sigma_i v_i \quad \text{ für } i=1, \dotsc, \min(m,n),}

d. h., die Paare aus Singulärwert und Singulärvektoren kennzeichnen Längenänderung und Richtung im Bildraum durch die lineare Transformation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} bzw. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M^T} , jeweils auf den Vektoren eines Orthonormalsystems im Urbildraum.

Ökonomische Variante der Singulärwertzerlegung

Sei

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M = U \Sigma V^*}

die Singulärwertzerlegung einer Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m\times n} -Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} .

Im Falle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m<n} gibt es eine „ökonomische Variante“ der Singulärwertzerlegung der Gestalt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M = U \Sigma_m V_m^*} .

Hierbei ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V_m} diejenige Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n \times m} -Matrix, deren Spalten aus den ersten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} Spalten von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V} bestehen, und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma_m} besteht aus den ersten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} Spalten von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma} .

Analog ist die ökonomische Variante im Falle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m>n} wie folgt gegeben:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M = U_n \Sigma_n V^*,}

wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle U_n} die ersten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Spalten von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle U} enthält und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma_n} die ersten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Zeilen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma} .

Viele Programmierbibliotheken für lineare Algebra können nur letztere Variante berechnen; für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m\times n} -Matrizen mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m<n} kann man die Singulärwertzerlegung (in ersterer Variante) dann durch Transposition bzw. Adjunktion erreichen:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M^* = V_m \Sigma_m^\top U^* } .

Numerische Bestimmung der Singulärwertzerlegung

Da die Singulärwerte mit den Eigenwerten der Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M^* M} zusammenhängen, wäre ein naheliegender Algorithmus zur numerischen Bestimmung einer Singulärwertzerlegung der Matrix die numerische Lösung des symmetrischen Eigenwertproblems zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M^* M} . Allerdings ist ein solcher Algorithmus numerisch instabil, da durch das Produkt die Konditionszahl quadriert wird, und zudem aufgrund der benötigten Matrizenprodukte auch sehr aufwendig.

In den 1960er Jahren entwickelte vor allem Gene Golub stabile iterative Algorithmen zur Berechnung einer Singulärwertzerlegung, die direkt die Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} transformieren, womit die Zerlegung praktisch nutzbar wurde. Diese gehen von der symmetrischen bzw. selbstadjungierten Blockmatrix

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{bmatrix}0&M\\M^\ast&0\end{bmatrix}}

aus, deren Eigenwerte die Singulärwerte und deren Negative sowie null sind. Das ursprüngliche Verfahren wurde von ihm 1965 mit William Kahan und ein iteratives 1970 mit Christian Reinsch veröffentlicht. Die Verfahren formen die Matrix zunächst in eine günstigere Gestalt um: Mit Hilfe von orthogonalen Transformationen – etwa Householdertransformationen – wird die Matrix auf Bidiagonalform gebracht. Nach diesem Zwischenschritt erlaubt eine modifizierte Form des QR-Algorithmus eine effiziente numerische Bestimmung der Singulärwerte. Der Aufwand liegt bei ca. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tfrac{4}{3}n^3 + \mathcal{O}\left(n^2\right)} arithmetischen Operationen.

Anwendung

Die Singulärwertzerlegung wird insbesondere in der numerischen Mathematik verwendet. Damit lassen sich beispielsweise fast singuläre lineare Gleichungssysteme im Rahmen rechentechnischer Genauigkeiten passabel lösen.

Die Singulärwertzerlegung ist die wichtigste numerische Methode in der geophysikalischen Inversion, bei der aus an der Erdoberfläche beobachteten geophysikalischen Signalen aus dem Erdinneren die Struktur des letzteren bestimmt werden kann. Besondere Anwendungen sind hier die seismische Tomographie und das Umkehrproblem der Potentialtheorie.

In der Statistik ist die Singulärwertzerlegung der rechnerische Kern der Hauptkomponentenanalyse, dort auch Karhunen-Loève-Transformation genannt.

Einige moderne Bildkompressionsverfahren beruhen auf einem Algorithmus, der das Bild (= Matrix aus Farbwerten) in eine Singulärwertzerlegung überführt, anschließend nur die stark von null verschiedenen Elemente der Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma} berücksichtigt und dann die zur Rückgewinnung der Matrix erforderlichen Vektoren sowie die verbliebenen Diagonalelemente speichert. Besonders effektiv ist diese Kompression bei bestimmten rechteckigen Mustern und natürlich desto effektiver, je größer (und je quadratähnlicher) das Bild ist. Dies ist eine mögliche Anwendung von Modellreduktion. Das Weglassen von kleinen Singulärwerten ist ein verlustbehaftetes Modellreduktionsverfahren.

In der Teilchenphysik benutzt man die Singulärwertzerlegung, um Massenmatrizen von Dirac-Teilchen zu diagonalisieren. Die Singulärwerte geben die Massen der Teilchen in ihren Masseneigenzuständen an. Aus den Transformationsmatrizen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle U} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V} konstruiert man Mischungsmatrizen wie die CKM-Matrix, die ausdrücken, dass die Masseneigenzustände von Teilchen aus einer Mischung von Flavour­eigenzuständen bestehen können.

Die Singulärwertzerlegung ist der Kern der Latent Semantic Analysis, eines Verfahrens des Information Retrieval, das hilft, in großen Textkollektionen latente Konzepte aufzudecken, anhand derer dann z. B. unterschiedlich bezeichnete Informationen zum gleichen Thema gefunden werden können.

In der Regelungstheorie ist Singulärwertzerlegung eine der Grundlagen für die Entwicklung von robusten Reglern.

Siehe auch

• Hauptkomponentenanalyse

Literatur

• Günter Gramlich: Anwendung der Linearen Algebra mit MATLAB^®. Carl Hanser Verlag, 2004. ISBN 3-446-22655-9.
• Peter Deuflhard und Andreas Hohmann: Numerische Mathematik I. Walter de Gruyter, Berlin 2008. ISBN 3-11-020354-5.
• Martin Hermann: Numerische Mathematik, Band 1: Algebraische Probleme. 4., überarbeitete und erweiterte Auflage. Walter de Gruyter Verlag. Berlin und Boston 2020. ISBN 978-3-11-065665-7.

Weblinks

• Gene H. Golub, William Kahan: Calculating the singular values and pseudo-inverse of a matrix. SIAM J. Numer. Anal., Serie B, Bd. 2 (1965), Nr. 2, S. 205–224. Online ebenso bei galton.uchicago.edu und bei www3.math.tu-berlin.de.
• Gilbert W. Stewart: On the early history of the singular value decomposition. SIAM Review, Bd. 35 (1993), Nr. 4, S. 551–566.
• taramath Online-Tool zur Berechnung der Singulärwertzerlegung reeller Matrizen.