Invertir una matriz de covarianza numéricamente estable

Question

Dado un $n\times n$ matriz de covarianza $C$ donde$n$$250$, tengo que calcular el $x\cdot C^{-1}\cdot x^t$ para muchos vectores $x \in \mathbb{R}^n$ (el problema viene de la aproximación de ruido por un $n$-dimensiones de la distribución Gaussiana).

¿Cuál es la mejor forma (en el sentido de que numéricamente estable) para resolver estas ecuaciones?

Una opción es la Descomposición de Cholesky, porque es numéricamente muy estable y rápida. Es el mayor complejidad computacional de la Descomposición de Valor Singular merece la pena? O hay otra posibilidad mejor?

Answer 1

Cholesky, suena como una buena opción por la siguiente razón: una vez que has hecho el de la factorización de Cholesky para obtener $C=LL^T$ donde $L$ es triangular, $x^TC^{-1}x = ||L^{-1}x||^2$, e $L^{-1}x$ es fácil de calcular, debido a que es un sistema triangular. Las desventajas de esto es que incluso si $C$ es escasa, $L$ es, probablemente, densa, y también que hacer la misma cantidad de trabajo para todos los $C$$x$, mientras que otros métodos puede permitir que usted para explotar alguna estructura especial y obtener buenas aproximaciones a la solución con menos trabajo. Por esas razones, también podría considerar la subespacios de Krylov métodos para calcular $C^{-1}x$, como conjugar los gradientes (desde $C$ es simétrica y definida positiva), especialmente si $C$ es escasa. $n=250$ no es terriblemente grande, pero todavía lo suficientemente grandes como subespacios de Krylov métodos se podría pagar si $C$ es lo suficientemente escasa. (No podría ser en realidad los métodos especiales de computación $x^TC^{-1}x$ a sí misma como opuesta a $C^{-1}x$, pero no sé de ninguna.)

Edit: Ya que usted se preocupa por la estabilidad, permítanme dirección: Cholesky es bastante estable, como nota. Conjugar los gradientes es notoriamente *onu*estable, sino que tiende a funcionar de todos modos, al parecer.