taralino

Reduktionsverfahren

Von zentraler Bedeutung für die Einsatzmöglichkeiten der Singulärwertzerlegung sind folgende Beobachtungen. Angenommen, ist eine beliebige (m × n)-Matrix und

ist eine Singulärwertzerlegung von . Zudem nehmen wir an, dass die Matrix mehr Spalten als Zeilen besitzt, dass also gilt.

Per Definition der Singulärwertzerlegung wissen wir, dass nur auf der Diagonalen Einträge haben kann, die ungleich Null sind. Mit anderen Worten: Die Spalten m+1 bis n der Matrix beinhalten keinerlei Informationen, sodass zur Darstellung der Matrix die Matrizen und reduziert werden können:

Zudem wissen wir, dass die Singulärwerte der Matrix absteigend sortiert und positiv (oder gleich Null) sind. Tatsächlich sind bei Anwendungen im Bereich des Data Science häufig sehr viele Singulärwerte Null oder fast Null. Dies bedeutet, dass die Matrizen weiter reduziert werden können, ohne einen größeren Informationsverlust befürchten zu müssen. Um genauer zu sein: Für ein sei

die (m × q)-Matrix, die aus den ersten Spalten von besteht,
die (q × q)-Matrix, die aus der oberen linken (q × q)-Matrix von besteht,
die (q × n)-Matrix, die aus den ersten Zeilen von besteht.

Damit erhalten wir die folgende Approximation der Matrix :

Je größer gewählt wird, desto besser ist die Approximation. Spätestens für gilt sogar Gleichheit. Als kleine Zusammenfassung:

Wenn viele Singulärwerte einer Matrix Null oder fast Null sind, dann können die Matrizen der Singulärwertzerlegung reduziert werden, ohne dass mit einem größeren Informationsverlust zu rechnen ist.

Sämtliche Beobachtungen zuvor lassen sich auch auf Fälle mit übertragen. Entsprechend kann die Vorgehensweise als allgemeines Kompressionsverfahren eingesetzt werden, wie wir in den nachfolgenden Abschnitten sehen werden. Im Bereich des Data Science gibt es zahlreiche weitere Einsatzmöglichkeiten, auf die wir in weiteren Kursen eingehen werden.

Der folgende Quellcode dient dazu, erste Erfahrungen mit dem Reduktionsverfahren sammeln zu können. Dabei müssen die reduzierten Matrizen nicht explizit aufgestellt werden: Die Matrixmultiplikationen werden anhand drei verschachtelter for-Schleifen durchgeführt.

Beispiel

Es wird die Singulärwertzerlegung eine (3 × 4)-Matrix bestimmt. Diese wird verwendet, um das zuvor beschriebene Reduktionsverfahren zu erproben.

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <script src="taralino.js"></script>
</head>
<body>
<script>

// Datensatz als Datenmatrix
var A = [
  [1, 2, 0, 3],
  [4, 3, 2, 5],
  [2, 2, 1, 3]
];

// Parameter zur Reduktion
var q = 2;

// Dimension der Datenmatrix
var m = A.length;
var n = A[0].length;

// Singulaerwertzerlegung bestimmen
var T = LinearAlgebra.svd(A);

// Null-Matrix mit gleicher Dimension wie A
var B = [];
for (var i = 0; i < m; i++) {
  B.push([]);
  for (var j = 0; j < n; j++) B[i].push(0);
};

// Approximation der Datenmatrix bestimmen
for (var i = 0; i < m; i++) {
  for (var j = 0; j < n; j++) {
    for (var k = 0; k < q; k++) B[i][j] += T.U[i][k] * T.S[k][k] * T.V[k][j];
  };
};

// Datenmatrix und Approximation ausgeben
Console.print(A);
Console.print(B);

</script>
</body>
</html>

Vorschau Download Kopie speichern

Aufgabe

Mache die mit dem Quellcode zuvor vertraut. Welche Zahlen für den Parameter q sind zulässig? Wie gut ist die Approximation der Datenmatrix in Abhängigkeit von q?