多元正態分佈的抽樣複雜性

多元正態分佈抽樣的計算複雜度是多少？多元正態分佈的抽樣複雜性

協方差矩陣是否需要先倒置，產生O（n^3）算法還是存在複雜度爲O（n^2）的算法？

2012-12-15 recursix

假設你想用給定的協方差結構生成許多隨機向量，所以任何分解等只需要在開始時只做一次。或者我誤解了你的問題？ – NPE

我正在計劃使用numpy.random.multivariate_normal函數。所以，我確實需要很多樣本，而攤銷成本很有趣。但是，如果我每次都要確保儘可能多地抽樣以分攤成本，那麼我就會流浪。在O（n^2）算法的情況下，我不必擔心這方面的問題。 – recursix

如果Ç是你的協方差矩陣，並且C = LL ^Ť是其Cholesky分解，然後Lx的將具有所需的協方差結構。這裏，x是一個n - 標準正態變量的向量。

喬列斯基分解需要O（n^3）時間來計算。但是，如果您事先做好準備，然後只使用L，那麼您將攤分所計算的所有隨機樣本的成本。

2012-12-15 18:59:31 NPE

查看numpy的mtrand.pyx文件，可以看到他們正在使用複雜度爲O（n^3）的svd分解。其他操作只是矩陣乘法和複雜度O（n^2）的添加。因此，爲每個功能調用分攤成本值得大量抽樣。 – recursix

回答