Niedrigrang-Approximation

Den wichtigen Teil einer Matrix behalten

Die SVD schreibt eine Matrix als Summe von Rang-eins-Schichten, $A=\sum_i\sigma_i\mathbf u_i\mathbf v_i^{T}$, von der größten zur kleinsten. Behält man nur die ersten $k$ Schichten, erhält man $A_k=U_k\Sigma_kV_k^{T}$, eine Matrix vom Rang $k$. Der Satz von Eckart und Young besagt, dass diese Abschneidung die beste Rang-$k$-Approximation überhaupt ist, ob der Fehler in der Frobenius- oder der Spektralnorm gemessen wird. Keine geschickte Wahl von $k$ Richtungen schlägt die ersten $k$ Singulärrichtungen.

Der Fehler besteht genau aus den verworfenen Singulärwerten, der behaltene Anteil der quadrierten Größe ist also $\sum_{i\le k}\sigma_i^2\big/\sum_i\sigma_i^2$, bei zentrierten Daten $A$ oft erklärte Varianz genannt. Eine Rang-$k$-Approximation einer $m\times n$-Matrix braucht nur $k(m+n+1)$ Zahlen statt $mn$, weshalb niedriger Rang auch Kompression ist. In der Finanzwelt sind die Schichten mit kleinem $\sigma_i$ überwiegend Stichprobenrauschen, ihr Abschneiden ist also Entrauschen, und $k$ wählt man per Schwelle für den behaltenen Anteil oder nach einer Lücke in den Singulärwerten.

• Eckart-Young: Das Abschneiden der SVD nach $k$ Termen ist in beiden Normen die beste Rang-$k$-Approximation.
• Fehler: Frobenius $\sqrt{\sum_{i>k}\sigma_i^2}$, spektral $\sigma_{k+1}$.
• Speicher: $k(m+n+1)$ Zahlen statt $mn$.

Lab: Was bewertet wird

• Der Frobenius-Fehler15 Pkt.
• Der behaltene Anteil15 Pkt.
• Eine Rang-eins-Approximation15 Pkt.
• Speicher einer Niedrigrang-Matrix10 Pkt.
• Der Satz von Eckart und Young15 Pkt.
• Eine Matrix komprimieren15 Pkt.
• Warum Abschneiden entrauscht15 Pkt.