给定A和B的痕量（AB^{ - 1}）的有效计算

我有两个平方矩阵A和B.A是对称的，B是对称正定。我想计算$ trace（A.B^{ - 1}）$。现在，我计算B的Cholesky分解，求解方程$ A = C.B $中的C并且总和对角元素。给定A和B的痕量（AB^{ - 1}）的有效计算

有没有更高效的治疗方法？

我打算使用Eigen。如果矩阵稀疏（A可以通常是对角线，B通常是带对角线），您可以提供一个实现吗？

来源

2011-09-22 yannick

我认为C++标签实际上属于这里，因为问题是关于使用Eigen（C++矩阵操作库）的实现。 –

是正半定还是正定？ –

@DavidZaslavsky我删除了标签 – yannick

如果B是稀疏的，也可能是有效的（即，O（N），假定的B良好条件数），以在

B x_i = a_i

求解x_i（样品Conjugate Gradient代码维基百科上给出）。以a_i为A的列向量，可以得到O（n^2）中的矩阵B^{-1} A。然后，您可以对对角元素进行求和以获得跟踪。一般来说，进行稀疏逆乘法比获取全集特征值更容易。 ~~为了比较，Cholesky decomposition是O（n^3）。~~（参见Darren Engwirda的关于Cholesky的评论）。

如果你只需要一个近似的痕迹，你其实可以通过在q随机向量r平均

r^T (A B^{-1}) r

降低成本至O（Q N）。通常是q << n。这是提供的随机矢量r的组分满足

< r_i r_j > = \delta_{ij}

其中<...>表示超过r分布的平均无偏估计。例如，组件r_i可以是具有单位方差的独立高斯分布。或者他们可以从+ -1统一选择。通常情况下，轨迹尺度如O（n）和轨迹估计中的误差如O（sqrt（n/q））缩放，因此相对误差按比例缩放为O（sqrt（1/nq））。

来源

2011-09-22 04:27:37

感谢您的回答。你如何用r进行平均？从你写的内容来看，似乎你需要计算A.B^{ - 1}，这可能不是你想说的。 – yannick

Kipton可能意味着您应该先计算B x = r然后计算r^T A x来计算r^T A B^{ - 1} r。但我不明白他是如何得到概率方法的O（n）成本的：解决n个成本为O（n）的系统，每个系统的成本为O（n^2）。也许随机向量的数量可以小于n = A的大小？ –

@Jitse，是的，谢谢你发现错字。 –

如果广义特征值计算效率更高，则可以计算广义特征值A*v = lambda* B *v，然后总结所有的lambda表达式。

来源

2011-09-22 01:39:50

给定A和B的痕量（AB^{ - 1}）的有效计算

回答

相关问题