Eigendecomposition Approximation mittels Formel

12.06.2017, 12:22	C.White	Auf diesen Beitrag antworten »
Eigendecomposition Approximation mittels Formel Meine Frage: Hallo, ich bin gerade dabei ein Paper zu bearbeiten, welches eine Formel enthält, die bei meiner manuellen Rechnung nicht funktioniert. Grundsätzlich beschäftigt sich die Problematik mit dem "rank-one update" Problem, welches Methoden sucht, um die Eigendecomposition einer Matrix zu aktualisieren, ohne die komplette Eigendecomposition erneut durchführen zu müssen, da diese viel Rechenpower benötigt. Die eigendecomposition einer Matrix K wäre also $\begin{eqnarray} K=V \Sigma V^T \end{eqnarray}$ , wobei V die Eigenvektoren und $\begin{eqnarray} \Sigma \end{eqnarray}$ die Diagonalmatrix der Eigenwerte ist. Nun ist folgendes gesucht: $\begin{eqnarray} <br /> K_t+\varphi\varphi^T = \begin{bmatrix}<br /> V && \frac{p}{\left \\| p \right \\|} <br /> \end{bmatrix}{\Sigma}'{\begin{bmatrix}<br /> V && \frac{p}{\left \\| p \right \\|} <br /> \end{bmatrix}}^T <br /> <br /> \end{eqnarray}$ mit $\begin{eqnarray} p = (I-VV^T)\varphi \end{eqnarray}$ . $\begin{eqnarray} K_t + \varphi\varphi^T \end{eqnarray}$ ist die Ausgangsmatrix K, welche mit einem Vektore $\begin{eqnarray} \varphi \end{eqnarray}$ erweitert wird. Von dieser neuen Matrix, wird also die neue Eigendecomposition gesucht, ohne diese erneut komplett durchführen zu müssen. Man kann diese wohl über die gegebene Formel berechnen. Grundsätzlich würde es reichen, sich erstmal auf den ersten Teil zu konzentrieren, dieser wäre ja $\begin{eqnarray} <br /> \left.\begin{matrix}<br /> \begin{bmatrix}<br /> V && \frac{p}{\left \\| p \right \\|} <br /> \end{bmatrix}<br /> \end{matrix}\right.<br /> \end{eqnarray}$ Meiner Ansicht nach müssten das ja die neuen Eigenvektoren sein. Wenn ich jetzt nur mal diesen Teil damit vergleiche, was ich rausbekomme, wenn ich die komplette Eigendecomposition mache, ist das Ergebnis einfach ein total anderes, da sich die Eigenvektoren komplett verändern. In der Formel wären V ja schonmal die alten Eigenvektoren, wie kann das klappen? Was verstehe ich hier total falsch? Einige Referenzen dazu: Radha Chitta, Jin & Jain 2016: "Stream Clustering: efficient kernel-based approximation using importance sampling" Brand, M. (2006): "Fast low-rank modications of the thin singular value decomposition", Linear Algebra and Its Applications). Meine Ideen: Rechenbeispiel: Gegeben sei: $\begin{eqnarray} <br /> K_{2} = \begin{bmatrix}<br /> 1 & 0.0173\\ <br /> 0.0173 & 1<br /> \end{bmatrix} \end{eqnarray}$ Die Eigenvektoren dafür lauten (Eigendecomposition): $\begin{eqnarray} <br /> V = \begin{bmatrix}<br /> 0.707 & -0.707 \\ <br /> 0.707 & 0.707 <br /> \end{bmatrix}<br /> \end{eqnarray}$ Nun die Matrix mit dem neuen Vektor $\begin{eqnarray} \varphi \end{eqnarray}$ : $\begin{eqnarray} <br /> K_{3} = \begin{bmatrix}<br /> 1 & 0.0173 & 0.895 \\ <br /> 0.0173 & 1 & 0.053 \\ <br /> 0.895 & 0.053 & 1<br /> \end{bmatrix}<br /> \end{eqnarray}$ Und die manuell berechneten Eigenvektoren (ohne die Update-Formel): $\begin{eqnarray} <br /> V = \begin{bmatrix}<br /> 0.7055 & 0.7063 & 0.059\\ <br /> 0.0553 & 0.0282 & -0.9981 \\<br /> 0.7066 & -0.7064 & 0.0192<br /> \end{bmatrix}<br /> \end{eqnarray}$ Wenn man diese Eigenvektoren mit der Formel berechnen will, müsste man ja eigentlich "nur" einsetzen. Bereits beim ersten Teil, der Errechnung von p erhalte ich jedoch eine 0-Matrix. Somit würde als neuer Eigenvektor 0 rauskommen, was ja nunmal nicht stimmt. Was mache ich falsch? $\begin{eqnarray} <br /> p = (I-VV^T)\varphi<br /> \end{eqnarray}$ Wenn ich jetzt rechne VV^T, d.h. $\begin{eqnarray} <br /> (I - \begin{bmatrix}<br /> 0.707 & -0.707 \\ <br /> 0.707 & 0.707 <br /> \end{bmatrix} * \begin{bmatrix}<br /> 0.707 & -0.707 \\ <br /> 0.707 & 0.707 <br /> \end{bmatrix}^T) = 0 <br /> \end{eqnarray*}$ Vielen Dank im Vorraus, ich hoffe die Infos reichen. Leider habe ich keine Mathematik studiert und tue mich deshalb etwas schwer damit.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »