cálculo eficiente de Trace (AB^{- 1}) dado A y B

Tengo dos matrices cuadradas A y B. A es simétrica, B es positivo simétrico definido. Me gustaría calcular $ trace (A.B^{- 1}) $. Por ahora, calculo la descomposición de Cholesky de B, resuelva C en la ecuación $ A = C.B $ y sume los elementos diagonales.cálculo eficiente de Trace (AB^{- 1}) dado A y B

¿Hay una forma más eficiente de proceder?

Planeo usar Eigen. ¿Podría proporcionar una implementación si las matrices son dispersas (A a menudo puede ser diagonal, B a menudo es diagonal de banda)?

Fuente

2011-09-22 yannick

Creo que la etiqueta C++ en realidad pertenece aquí, ya que la pregunta es acerca de una implementación utilizando Eigen, una biblioteca de manipulación de matrices C++. –

¿Es un positivo semidefinido o positivo definido? –

@DavidZaslavsky Quité la etiqueta – yannick

Si B es escasa, puede ser eficiente (es decir, O (n), suponiendo buen estado número de B) para resolver para x_i en

B x_i = a_i

(muestra Conjugate Gradient código se da en Wikipedia). Tomando a_i para ser los vectores columna de A, obtienes la matriz B^{-1} A en O (n^2). Luego puede sumar los elementos diagonales para obtener la traza. En general, es más fácil hacer esta multiplicación inversa dispersa que obtener el conjunto completo de valores propios. ~~Para comparar, Cholesky decomposition es O (n^3).~~ (ver el comentario de Darren Engwirda a continuación sobre Cholesky).

Si sólo necesita una aproximación a la huella, en realidad se puede reducir el costo de O (q n) promediando

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

sobre q vectores aleatorios r. Por lo general, q << n. Esta es una estimación no sesgada a condición de que los componentes del vector aleatorio r satisfacen

< r_i r_j > = \delta_{ij}

donde <...> indica un promedio sobre la distribución de r. Por ejemplo, los componentes r_i podrían ser independientes gaussianos distribuidos con la unidad de varianza. O podrían seleccionarse uniformemente desde + -1. Normalmente, las escalas de traza como O (n) y el error en la estimación de traza se escalan como O (sqrt (n/q)), por lo que el error relativo se escala como O (sqrt (1/nq)).

Fuente

2011-09-22 04:27:37

Gracias por su respuesta. ¿Cómo se hace el promedio con r? según lo que escribe, parece que necesita calcular A.B^{- 1}, que probablemente no sea lo que quería decir. – yannick

Kipton probablemente significa que debe calcular r^T A B^{- 1} r resolviendo primero B x = r y luego calcula r^T A x. Pero no veo cómo obtiene un costo de O (n) para el enfoque probabilístico: resolver n sistemas con costo O (n) da un costo de O (n^2). Quizás el número de vectores aleatorios se puede tomar más pequeño que n = tamaño de A? –

@Jitse, sí, gracias por encontrar el error tipográfico. –

Si los valores propios generalizados son más eficientes para calcular, puede calcular los valores propios generalizados, A*v = lambda* B *v y luego sumar todas las lambdas.

Fuente

2011-09-22 01:39:50

cálculo eficiente de Trace (AB^{- 1}) dado A y B

Respuesta

Cuestiones relacionadas