Saya ingin menggambar sampel . Wikipedia menyarankan untuk menggunakan komposisi Cholesky atau Eigend , yaitu atau
Dan karenanya sampel dapat diambil melalui: atau mana
Wikipedia menyatakan bahwa keduanya sama-sama bagus untuk menghasilkan sampel, tetapi metode Cholesky memiliki waktu komputasi yang lebih cepat. Apakah ini benar? Khususnya secara numerik ketika menggunakan metode monte-carlo, di mana varians sepanjang diagonal mungkin berbeda dengan beberapa urutan besarnya? Apakah ada analisis formal tentang masalah ini?
car::ellipse
) . Meskipun pertanyaannya diajukan dalam aplikasi yang berbeda, teori di baliknya adalah sama. Anda akan melihat angka-angka bagus untuk penjelasan geometris di sana.Jawaban:
Masalahnya dipelajari oleh Straka et.al untuk Filter Kalman Unscented yang mengambil (deterministik) sampel dari distribusi Normal multivariat sebagai bagian dari algoritma. Dengan sedikit keberuntungan, hasilnya mungkin berlaku untuk masalah monte-carlo.
Cholesky Decomposition (CD) dan Eigen Decomposition (ED) - dan dalam hal ini Matrix Square Root (MSR) yang sebenarnya adalah semua cara di mana matriks semi-definite positif (PSD) positif dapat dipecah.
Pertimbangkan SVD dari matriks PSD, . Karena P adalah PSD, ini sebenarnya sama dengan ED dengan P = U S U T . Selain itu, kita dapat membagi matriks diagonal dengan akar kuadratnya: P = U √P=USVT P=USUT , mencatat itu√P=US−−√S−−√TUT .S−−√=S−−√T
Kami sekarang dapat memperkenalkan matriks ortogonal sewenang-wenang :O
.P=US−−√OOTS−−√TUT=(US−−√O)(US−−√O)T
Pilihan sebenarnya mempengaruhi kinerja estimasi, terutama ketika ada elemen off-diagonal yang kuat dari matriks kovarians.O
Makalah ini mempelajari tiga pilihan :O
Dari mana kesimpulan berikut diambil di koran setelah banyak analisis (mengutip):
Referensi:
sumber
Berikut ini adalah ilustrasi sederhana menggunakan R untuk membandingkan waktu komputasi dari kedua metode.
Waktu berjalan adalah
Ketika meningkatkan ukuran sampel menjadi 10.000, waktu berjalan adalah
Semoga ini membantu.
sumber
Inilah manual, atau demonstrasi orang miskin, buktikan-kepada-saya sendiri:
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:sumber
microbenchmark
and it really makes a difference.