Chciałbym narysować próbkę . Wikipedia sugeruje albo stosując Cholesky'iego lub Eigendecomposition , tj i
Stąd przykład można pobrać za pomocą: lub gdzie \ mathbf {v} \ sim N \ left (\ mathbf {0}, \ mathbf {I} \ right)
Wikipedia sugeruje, że oba są równie dobre do generowania próbek, ale metoda Cholesky'ego ma szybszy czas obliczeń. Czy to prawda? Zwłaszcza numerycznie przy zastosowaniu metody Monte Carlo, gdzie wariancje wzdłuż przekątnych mogą się różnić o kilka rzędów wielkości? Czy jest jakaś formalna analiza tego problemu?
car::ellipse
) . Chociaż pytanie jest zadawane w różnych zastosowaniach, leżąca u podstaw teoria jest taka sama. Zobaczysz tam ładne figury do geometrycznego wyjaśnienia.Odpowiedzi:
Problem został zbadany przez Straka i in. Dla Unscented Kalman Filter, który pobiera (deterministyczne) próbki z wielowymiarowego rozkładu normalnego jako części algorytmu. Przy odrobinie szczęścia wyniki mogą odnosić się do problemu Monte Carlo.
Rozkład Cholesky'ego (CD) i rozkład własny (ED) - i w tym przypadku faktyczny pierwiastek kwadratowy macierzy (MSR) to wszystkie sposoby, w jakie można rozbić dodatnią półokreśloną macierz (PSD).
Rozważmy SVD matrycy PSD, . Ponieważ P PSD, jest w rzeczywistości taka sama, jak z ED P = U S U T . Co więcej, możemy podzielić macierz diagonalną przez jej pierwiastek kwadratowy: P = U √P=USVT P=USUT , zauważając, że√P=US−−√S−−√TUT .S−−√=S−−√T
Możemy teraz wprowadzić dowolną macierz ortogonalną :O
.P=US−−√OOTS−−√TUT=(US−−√O)(US−−√O)T
Wybór faktycznie wpływa na wydajność estymacji, szczególnie gdy występują silne nie-diagonalne elementy macierzy kowariancji.O
W pracy przeanalizowano trzy opcje :O
Z których po wielu analizach (cytowaniu) wyciągnięto następujące wnioski:
Odniesienie:
źródło
Oto prosta ilustracja wykorzystująca R do porównania czasu obliczeń dwóch metod.
Czasy działania są następujące
Przy zwiększaniu wielkości próbki do 10000 czasy działania są następujące
Mam nadzieję że to pomoże.
źródło
Oto instrukcja manualna lub pokaz biednego człowieka, który udowodni mi:
1. METODA SVD:
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:źródło
microbenchmark
and it really makes a difference.