SVD zum Ermitteln des größten Eigenwerts einer 50x50-Matrix - Verschwende ich viel Zeit?

Ich habe ein Programm, das den größten Eigenwert vieler reeller symmetrischer 50x50-Matrizen berechnet, indem es Singulärwertzerlegungen für alle durchführt. Die SVD ist ein Engpass im Programm.

Gibt es Algorithmen, die viel schneller den größten Eigenwert finden, oder würde eine Optimierung dieses Teils nicht viel Kapitalrendite bringen?

linear-algebra eigensystem Anna
quelle

Können Sie weitere Informationen zu Ihren Matrizen geben, z. B. wenn etwas über ihre Struktur, den Bereich ihrer Eigenwerte oder ihre Ähnlichkeit bekannt ist?

Pedro

Es ist eine Kovarianzmatrix (

). Tests haben ergeben, dass alle bis auf die 5 größten Eigenwerte nahe bei Null liegen und dass der größte Eigenwert mindestens ~ 20% größer ist als der zweitgrößte. Da es viele Eigenwerte in der Nähe von Null gibt, ist der Bereich vermutlich nicht wichtig? Es kann auf jeden Bereich neu skaliert werden. Die Skala, die ich derzeit benutze, reicht von 150 bis 200.

X X^{T}

$XX^T$

Anna

Außerdem ist die Matrix nicht sehr genau singulär, sodass das SVD-Problem gut konditioniert ist.

Anna

symmetrisch und positiv (semi) definit ist, können Sie die Cholesky-Faktorisierung anstelle der SVD verwenden. Die Cholesky-Faktorisierung benötigt viel weniger Flops zur Berechnung als die SVD, aber als genaue Methode werden immer noch

Flops benötigt.

X X^{T}

$XX^T$

O (n^{3})

$O(n^3)$

Ken

@Anna: Haben Sie einen der vielen hier vorgeschlagenen Ansätze ausprobiert? Ich wäre gespannt, was für Sie in der Praxis am besten funktioniert hat ...

Pedro

Antworten:

Abhängig von der Genauigkeit, die Sie für den größten Eigenwert benötigen, können Sie die Power-Iteration verwenden .

Für Ihr spezielles Beispiel würde ich so weit gehen, dass ich nicht explizit bilde, sondern in jeder Iteration berechne . Die Berechnung von würde -Operationen erfordern, wohingegen das Matrixvektorprodukt nur erfordert . $A=XX^\mathsf{T}$ $x \leftarrow X(X^\mathsf{T}x)$ $A$ $\mathcal O(n^3)$ $\mathcal O(n^2)$

Die Konvergenzrate hängt von der Trennung zwischen den beiden größten Eigenwerten ab. Dies ist daher möglicherweise nicht in allen Fällen eine gute Lösung.

Pedro
quelle

Wenn der größte Eigenwert 20% größer ist als der nächste, sollte die Potenz-Iteration ziemlich schnell konvergieren (alle anderen Eigenwerte werden in jeder Iteration um den Faktor 5/6 gedämpft, sodass Sie für jeweils 13 Iterationen eine Ziffer erhalten.

Wolfgang Bangerth

Krylov-Subraummethoden sind strikt besser als Potenzmethoden, da sie den Vektor der Potenziteration mit der gleichen Anzahl von Iterationen enthalten.

Jack Poulson

@ JackPoulson: Ja, aber jede Iteration ist teurer zu berechnen ... Wäre es das wirklich wert für ein so kleines Problem?

Pedro

@Pedro: Natürlich erfordern die Matvecs quadratische Arbeit, und die Rayleigh-Quotienten-Eigenauflösung und die anschließende Expansion sind im Vergleich trivial.

Jack Poulson

Code-Aufwand? Da @JackPoulson angeschnitten die Frage, B. Parlett et al (1982) ( „On Abschätzen der größten Eigenwert mit dem Lanczos - Algorithmus“) vergleichen Leistung Methode, Strom Methode + Aitken Beschleunigung und eine Anwendung von Lanczos den größten Eigenwert eines echten Targeting symmetrisch (oder hermitisch) pos. def. Matrix. Sie kommen zu dem Schluss, dass die Lanczos-Methode effizienter ist, wenn sogar eine bescheidene Genauigkeit (des ersten Eigenwerts im Verhältnis zum zweiten) erforderlich ist und Fehlkonvergenz besser vermieden werden kann.

Hardmath

Wenn nur 5 Eigenwerte sehr signifikant sind, sollte der Lanczsos-Algorithmus mit als Matrixvektor-Multiplikation nach 5 Anfangsschritten eine schnelle lineare Konvergenz ergeben, daher ein ziemlich genauer größter Eigenwert mit wenigen Iterationen. $X(X^Tx)$

Arnold Neumaier
quelle

Sind Sie (@ArnoldNeumaier) Denken von etwas wie diese , in geeigneter Weise vereinfacht (

)? Es ist interessant, dass es eine andere Annäherung als Lanczos gibt, wenn ein dritter Vektor über demselben Krylov-Unterraum beibehalten wird.

B = T = I

$B = T = I$

Hardmath

Nein; Ich meinte den Standard-Lanczsos-Algorithmus, hatte es aber eilig, CG zu schreiben. Jetzt korrigiert.

Arnold Neumaier

Für eine positive semi-definite Matrix wie kann es sich lohnen, die Konvergenz mit einer Spektrumverschiebung zu beschleunigen . Das heißt, ein geeigneter Skalar wird ausgewählt und die Potenzmethode wird auf anstelle von angewendet . $A = XX^T$ $\mu$ $A - \mu I$ $A$

Ein paar Wiederholungen der Grundleistung Methode sollten Sie eine grobe Schätzung geben des größten Eigenwertes . Angenommen, der dominante Eigenwert hat die Multiplizität 1 und alle anderen sind in $||Ax||/||x||$ $\lambda_1$ , dann $[0,\frac{5}{6} \lambda_1]$ hätte den größten Eigenwert $A - \frac{5}{12} \lambda_1 I$ und der Rest in $\frac{7}{12} \lambda_1$ . $[\frac{-5}{12} \lambda_1, \frac{5}{12} \lambda_1]$

Mit anderen Worten, Sie würden die Dominanz des größten Eigenwerts von 20% über den nächstgrößeren auf 40% über den nächstgrößeren (absoluten Wert eines) Eigenwerts erhöhen. Die geometrische Konvergenz der Potenzmethode würde sich entsprechend beschleunigen. Sobald der größte Eigenwert von mit ausreichender Genauigkeit gefunden wurde, wird geschätzt, indem die Verschiebung , die weggenommen wurde, zurückaddiert wird. $A - \mu I$ $\lambda_1$ $\mu$

$A - \mu I$ $(A - \mu I)x = X(X^Tx) - \mu x$ $O(n^2)$

Hardmath
quelle

Dies scheint eine gute Vorstellung davon zu erfordern, wie groß der zweitgrößte Eigenwert ist. Wie würden Sie es in einem solchen Fall schätzen?

Pedro

λ_{1}

$\lambda_1$

| λ_{2} | / | λ_{1} |

$|\lambda_2|/|\lambda_1|$

| λ_{2} | / | λ_{1} |

$|\lambda_2|/|\lambda_1|$

λ_{2}

$\lambda_2$ relative to

λ_{1}

$\lambda_1$ if desired. I was suggesting what benefit you'd see in a case such as Anna describes in her comments below the Question.

hardmath