Ich würde gerne eine Probe ziehen . Wikipedia schlägt vor, entweder Cholesky oder Eigendecomposition zu verwenden , dh oder
Und daher kann die Probe gezogen werden über: oder wo
Wikipedia schlägt vor, dass beide gleich gut für die Generierung von Samples geeignet sind, aber die Cholesky-Methode hat die schnellere Rechenzeit. Ist das wahr? Besonders numerisch bei Verwendung einer Monte-Carlo-Methode, bei der sich die Varianzen entlang der Diagonalen um mehrere Größenordnungen unterscheiden können? Gibt es eine formale Analyse zu diesem Problem?
car::ellipse
) . Obwohl die Frage in verschiedenen Anwendungen gestellt wird, ist die Theorie dahinter dieselbe. Dort sehen Sie schöne Figuren zur geometrischen Erklärung.Antworten:
Das Problem wurde von Straka et al. Für den Unscented Kalman Filter untersucht, der als Teil des Algorithmus (deterministische) Stichproben aus einer multivariaten Normalverteilung zieht. Mit etwas Glück könnten die Ergebnisse auf das Monte-Carlo-Problem zutreffen.
Die Cholesky-Dekomposition (CD) und die Eigen-Dekomposition (ED) - und im Übrigen die eigentliche Matrix-Quadratwurzel (MSR) - sind alle Möglichkeiten, wie eine positive semi-definite Matrix (PSD) zerlegt werden kann.
Betrachten sie den SVD eine PSD - Matrix . Da P PSD ist, ist dies tatsächlich das gleiche wie der ED mit P = U S U T . Außerdem können wir die Diagonalmatrix durch ihre Quadratwurzel teilen: P = U √P=USVT P=USUT unter Hinweis darauf, dass√P=US−−√S−−√TUT .S−−√=S−−√T
Wir können nun eine beliebige orthogonale Matrix einführen :O
.P=US−−√OOTS−−√TUT=(US−−√O)(US−−√O)T
Die Wahl von wirkt sich tatsächlich auf die Schätzleistung aus, insbesondere wenn die Kovarianzmatrix stark von der Diagonale abweicht.O
Die Arbeit untersuchte drei Möglichkeiten von :O
Daraus wurden nach eingehender Analyse (Zitieren) die folgenden Schlussfolgerungen gezogen:
Referenz:
quelle
Hier ist eine einfache Abbildung, in der R verwendet wird, um die Berechnungszeit der beiden Methoden zu vergleichen.
Die Laufzeiten sind
Wenn Sie die Stichprobengröße auf 10000 erhöhen, sind die Laufzeiten gleich
Hoffe das hilft.
quelle
Hier ist die manuelle oder arme Demonstration:
1. SVD METHOD:
2. CHOLESKY METHOD:
Thank you to @userr11852 for pointing out to me that there is a better way to calculate the difference in performance between SVD and Cholesky, in favor of the latter, using the function
microbenchmark
. At his suggestion, here is the result:quelle
microbenchmark
and it really makes a difference.