私は2つの正方行列AとBを持っています。Aは対称であり、Bは対称の正定値です。 $ trace（A.B^{ - 1}）$を計算したいと思います。ここでは、Bのコレスキー分解を計算し、方程式$ A = C.B $でCを解き、対角要素を合計します。AとBを指定したTrace（AB^{-1}）の効率的な計算
さらに効率的な方法がありますか？
私はEigenを使用する予定です。行列が疎である場合（Aはしばしば対角行列、Bはしばしば対角行列）、実装を提供できますか？
Bが疎である場合、それは（サンプルConjugate Gradientコードはウィキペディアに与えられる）
B x_i = a_i
にx_iについて解く（Bの良好な状態数を仮定すると、すなわち、O（n））が効率的であり得ます。 a_iをAの列ベクトルにすると、O（n^2）の行列B^{-1} Aが得られます。次に、対角要素を合計してトレースを取得することができます。一般に、固有値の完全な集合を得るよりも、この疎な逆数乗算を行う方が簡単です。 比較のために、Cholesky decompositionはO（n^3）です。（）CholeskyについてのDarren Engwirdaのコメントを参照してください。
あなただけのトレースの近似が必要な場合は、あなたが実際に
r^T (A B^{-1}) r
q以上のランダムベクトルrを平均化することにより、O（Q n）でのコストを削減することができます。通常q << n。これは、ランダムベクトルの成分はr<...>がrの分布の平均を示し
< r_i r_j > = \delta_{ij}
を満足することが提供される不偏推定値です。例えば、コンポーネントr_iは、単位分散を伴う独立したガウス分布であってもよい。または、それらは+ -1から一様に選択できます。一般的にO（n）のようなトレーススケールと、O（sqrt（n/q））のようなトレース推定の誤差は、の相対の誤差はO（sqrt（1/nq））となります。
あなたの答えをありがとう。あなたはrで平均化をどうやってやりますか？あなたが書いたものから、A.B^{ - 1}を計算する必要があるように思えますが、これはおそらくあなたが言うことではありません。 – yannick
Kiptonはおそらく、まずB x = rを解いてr^T A A xを計算することによってr^T A B^{ - 1} rを計算すべきことを意味します。しかし、私は確率論的アプローチのために彼がO（n）のコストをどのように得るのか見ていない。それぞれコストがO（n）のn個のシステムを解くとO（n^2）のコストがかかる。おそらく、ランダムベクトルの数は、n = Aのサイズよりも小さく取ることができるだろうか？ –
@Jitse、はい、タイプミスを見つけてくれてありがとう。 –
一般化された固有値が計算する方が効率的であれば、一般化された固有値A*v = lambda* B *vを計算してから、すべてのラムダを集計することができます。
私はC++タグが実際にここに属していると思います。なぜなら、質問はC++の行列操作ライブラリであるEigenを使った実装なので、ここに属しています。 –
は正の半正定値か正定値ですか？ –
@DavidZaslavskyタグを削除しました – yannick