yan*_*ick 6 math matrix sparse-matrix eigen
我有两个平方矩阵A和B.A是对称的,B是对称的正定.我想计算$ trace(AB ^ { - 1})$.现在,我计算B的Cholesky分解,求解方程$ A = CB $中的C并总结对角元素.
有更有效的方法吗？
我计划使用Eigen.如果矩阵稀疏(A通常是对角线,B通常是带对角线),你能提供一个实现吗？
如果B是稀疏的,也可能是有效的(即,O(N),假定的良好状态数B),以解决x_i在
B x_i = a_i
(样本共轭梯度代码在维基百科上给出).将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)).