math - 给定 A 和 B 的 Trace(AB^{-1}) 的有效计算

Question

我有两个方阵 A 和 B。A 是对称的，B 是对称正定的。我想计算 $trace(AB^{-1})$。现在，我计算 B 的 Cholesky 分解，在方程 $A=CB$ 中求解 C，并对对角线元素求和。

有没有更有效的处理方式？

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

Answer 1

如果B是稀疏的，它可能是有效的（即 O(n)，假设 的良好条件数）B解决x_i

B x_i = a_i

（示例共轭梯度代码在 Wikipedia 上给出）。取a_i的列向量A，得到B^{-1} AO(n^2) 中的矩阵。然后您可以对对角线元素求和以获得迹线。通常，执行这种稀疏逆乘法比获得完整的特征值集更容易。为了比较，Cholesky 分解是 O(n^3)。（请参阅下面关于 Cholesky 的 Darren Engwirda 的评论）。

如果您只需要跟踪的近似值，您实际上可以通过平均将成本降低到 O(qn)

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

在q随机向量r上。通常q << n. 这是一个无偏估计，前提是随机向量的分量r满足

< r_i r_j > = \delta_{ij}

其中< ... >表示 的分布的平均值r。例如，分量r_i可以是具有单位方差的独立高斯分布。或者它们可以从 +-1 中统一选择。通常，轨迹的比例为 O(n)，轨迹估计中的误差的比例为 O(sqrt(n/q))，因此相对误差的比例为 O(sqrt(1/nq))。

Answer 2

如果广义特征值的计算效率更高，则可以计算广义特征值，A*v = lambda* B *v然后对所有 lambda 求和。