Singulärwertzerlegung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Singulärwertzerlegung am Beispiel einer 2-dimensionalen, 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* und eine Dehnung/Stauchung Σ entlang der Koordinatenachsen. Die Singulärwerte σ1 und σ2 sind gerade 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 (Abk.: SWZ oder SVD für Singular Value Decomposition) 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 nicht-quadratische Matrizen.

Definition[Bearbeiten]

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

M \,=\, U \Sigma V^*

wobei

\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\cdots\geq\sigma_r> 0 ist.

Die positiven Diagonaleinträge \sigma_i, i=1,\dots,r von \Sigma heißen Singulärwerte von M.[1] Die Singulärwerte und damit auch die Matrix \Sigma sind durch M eindeutig bestimmt.
Die Spaltenvektoren u_i, i=1,...,m von U heißen Links-Singulärvektoren, die Spaltenvektoren v_i, i=1,...,n von V heißen Rechts-Singulärvektoren (zum Index i) der Matrix M.

Eigenschaften[Bearbeiten]

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.

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 \kappa_2(M)=\tfrac{\sigma_1}{\sigma_n}.

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

|\det(M)|=\prod_{i=1}^r \sigma_i,

falls M eine quadratische Matrix mit \det(M) \neq 0 ist.

Es gilt

M v_i = \sigma_i u_i

und

M^T u_i = \sigma_i v_i \quad \mathrm{f\ddot ur} \; i=1,\ldots,\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 M bzw. M^T, jeweils auf den Vektoren eines Orthonormalsystems im Urbildraum.

Numerische Bestimmung der Singulärwertzerlegung[Bearbeiten]

Da die Singulärwerte mit den Eigenwerten der Matrix M^\ast M zusammenhängen, wäre ein naheliegender Algorithmus zur numerischen Bestimmung einer Singulärwertzerlegung der Matrix die numerische Lösung des symmetrischen Eigenwertproblems zu M^\ast 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 aufwändig.

In den 1960er Jahren entwickelte vor allem Gene Golub stabile iterative Algorithmen zur Berechnung einer Singulärwertzerlegung, die direkt die Matrix M transformieren, womit die Zerlegung praktisch nutzbar wurde. Diese gehen von der symmetrischen bzw. selbstadjungierten Blockmatrix

\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 durch Householder-Transformationen – 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. \tfrac{4}{3}n^3 + \mathcal{O}\left(n^2\right) arithmetischen Operationen.

Anwendung[Bearbeiten]

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.

In der Statistik ist die SVD 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 SVD überführt, anschließend nur die stark von null verschieden Elemente der Matrix \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 umso 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 U und V konstruiert man Mischungsmatrizen wie die CKM-Matrix, die ausdrücken, dass die Masseneigenzustände von Teilchen aus einer Mischung von Flavoreigenzustä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 sie eine der Grundlagen für die Entwicklung von robusten Reglern.

Literatur[Bearbeiten]

Fußnoten[Bearbeiten]

  1. Der größte und kleinste Singulärwert einer quadratischen Matrix wurde Mitte des 20. Jahrhunderts auch als „obere Grenze“ bzw. „untere Grenze“ der Matrix bezeichnet, siehe Grenze (obere u. untere) einer quadratischen Matrix. In: J. Naas, H. L. Schmid: Mathematisches Wörterbuch. B. G. Teubner, Stuttgart, 1979, ISBN 3-519-02400-4.

Weblinks[Bearbeiten]