Singularwert-Rechner - SVD-Matrixzerlegung

Die Singulärwertzerlegung (SVD) ist eine der wichtigsten Faktorisierungen in der linearen Algebra. Für jede reelle m×n-Matrix A schreibt die SVD A als A = UΣV^T, wobei U eine m×m orthogonale Matrix ist, Σ eine m×n-Diagonalmatrix mit nichtnegativen Einträgen auf der Diagonale und V eine n×n orthogonale Matrix. Die Diagonaleinträge σ₁ ≥ σ₂ ≥ … ≥ 0 von Σ sind die Singularwerte von A. Singularwerte sind immer nichtnegative reelle Zahlen, selbst wenn die Ausgangsmatrix negative Einträge oder komplexe Struktur enthält. Sie sind durch die Matrix eindeutig bestimmt — im Gegensatz zu den Vektoren U und V, die bei mehrfachen Singularwerten nicht eindeutig sein können. Die Anzahl der von null verschiedenen Singularwerte entspricht dem Rang der Matrix, der die Dimension des Spaltenraums misst (die Menge aller möglichen Ausgaben der durch A dargestellten linearen Abbildung). Der Zusammenhang zwischen SVD und Eigenwerten ist präzise: Die Singularwerte von A sind die Quadratwurzeln der Eigenwerte der symmetrisch positiv semidefiniten Matrix A^T·A (bzw. äquivalent A·A^T für die linken Singulärvektoren). Dieser Rechner bildet A^T·A und wendet den Jacobi-Eigenwertalgorithmus an — ein iteratives Verfahren, das die Nebendiagonalelemente einer symmetrischen Matrix durch eine Folge orthogonaler Rotationen, sogenannte Givens-Rotationen, auf Null setzt — um die Eigenwerte zu bestimmen und daraus die Quadratwurzeln zu ziehen. Der größte Singularwert σ₁ entspricht der Spektralnorm (auch 2-Norm oder Operatornorm genannt) der Matrix — dem maximalen Faktor, um den die Matrix einen Einheitsvektor strecken kann. Die Frobenius-Norm ist die Quadratwurzel aus der Summe aller quadrierten Singularwerte und entspricht zugleich der Quadratwurzel aus der Summe aller quadrierten Matrixeinträge. Diese Normen sind praktisch bedeutsam: Die Frobenius-Norm ist das natürlichste Maß für die gesamte Energie einer Matrix, während die Spektralnorm die Empfindlichkeit gegenüber Störungen kontrolliert. Die Konditionszahl κ = σ₁/σₙ (Verhältnis des größten zum kleinsten Singularwert) quantifiziert, wie gut konditioniert die Matrix für die Lösung linearer Gleichungssysteme ist. Eine Konditionszahl nahe 1 bedeutet, dass das System gut konditioniert und genau lösbar ist. Eine sehr große Konditionszahl — etwa über 10⁶ oder 10¹² — weist auf ein schlecht konditioniertes System hin, bei dem kleine Störungen der Eingabe große Änderungen in der Lösung verursachen können, eine häufige Quelle numerischer Instabilität in wissenschaftlichem Rechnen und maschinellem Lernen. SVD hat ein bemerkenswert breites Anwendungsspektrum. In der Datenwissenschaft ist die Hauptkomponentenanalyse (PCA) — das Arbeitspferd der Dimensionsreduktion — mathematisch äquivalent zur SVD der zentrierten Datenmatrix. Die Hauptkomponenten sind die rechten Singulärvektoren V, und die durch jede Komponente erklärte Varianz ist proportional zum Quadrat des zugehörigen Singularwerts. In der Bildverarbeitung und -kompression erzeugt das Beibehalten nur der k größten Singularwerte und ihrer zugehörigen Vektoren eine Rang-k-Approximation der Bildmatrix, die den Fehler in Frobenius-Norm unter allen Rang-k-Matrizen minimiert — das ist der Eckart-Young-Satz. In Empfehlungssystemen (Collaborative Filtering) wird die Matrixfaktorisierung mittels SVD verwendet, um Nutzerbewertungen für unbekannte Elemente vorherzusagen. In der Ingenieurwissenschaft liefert die Pseudoinverse A† = VΣ†U^T die Minimum-Norm-Lösung im kleinsten-Quadrate-Sinn für über- oder unterbestimmte Systeme, was in Robotik, Regelungstheorie und Signalverarbeitung entscheidend ist. Für diesen Rechner werden Matrizen bis ungefähr 10×10 zuverlässig mit dem Jacobi-Algorithmus verarbeitet. Sehr große Matrizen oder Matrizen mit vielen nahezu identischen Singularwerten können aufgrund kumulierter Gleitkomma-Rundungsfehler etwas an Genauigkeit verlieren, doch die Ergebnisse sind für typische Eingaben mit mindestens sechs signifikanten Stellen genau.