Cholesky – Quantum Insights

Esta va a ser una entrada «utilitaria»: poca explicación, pero aportando código fuente, por si alguien lo necesita. ¿Recuerda la entrada en la que presenté la descomposición de Cholesky? En aquel momento, no incluí el algoritmo de la descomposición, porque quería experimentar un poco con la implementación. Ya lo he hecho, y estoy más o menos satisfecho con el resultado.

Antes de ver el código, le explico el contexto. Este es un método de una estructura Matrix, que encapsula solamente una matriz bidimensional de valores flotantes (campo values). Dentro de la estructura se definen todos los operadores y métodos que podéis imaginar. En paralelo, defino otra estructura, LowerMatrix, para representar matrices triangulares inferiores. No hay relaciones de herencia, al tratarse de estructura, pero la clase de matrices triangulares permite definir métodos y operadores más eficientes. Es importante tener en cuenta que LowerMatrix gasta exactamente la misma memoria que Matrix. La ventaja está en esos métodos que evitan procesar las dos mitades de la matriz.

También hace falta saber que he definido operadores de conversión implícitos que transforman un array bidimensional en uno u otro tipo de matrices. Este operador es el que me permite evitar un constructor explícito para devolver un valor en el método:

public unsafe LowerMatrix Cholesky()
{
    int n = Rows;
    double[,] dest = new double[n, n];
    double[,] src = values;
    double* tmp = stackalloc double[n + n];

    // First column is special.
    double ajj = src[0, 0];
    if (ajj <= 0)
    {
        dest[0, 0] = double.NaN;
        return dest;
    }
    dest[0, 0] = ajj = Math.Sqrt(ajj);
    double r = 1 / ajj;
    n--;
    for (int i = 1; i <= n; i++)
        dest[i, 0] = src[i, 0] * r;
    for (int j = 1; j <= n; j++)
    {
        // Compute the diagonal cell.
        double v = 0.0;
        for (int i = 0; i < j; i++)
        {
            double a = dest[j, i];
            v += a * a;
        }
        ajj = src[j, j] - v;
        if (ajj <= 0)
        {
            dest[j, j] = double.NaN;
            return dest;
        }
        dest[j, j] = ajj = Math.Sqrt(ajj);

        // Compute the other cells of column J.
        if (j < n)
        {
            r = 1 / ajj;
            for (int i = 0; i < j; i++)
                tmp[i] = dest[j, i];
            for (int i = j; i < n; i++)
            {
                v = 0.0;
                for (int k = 0; k < j; k++)
                    v += dest[i + 1, k] * tmp[k];
                tmp[i] = v;
            }
            for (int i = j; i < n; i++)
                dest[i + 1, j] = (src[i + 1, j] - tmp[i]) * r;
        }
    }
    return dest;
}

Sobre el algoritmo, en sí: el algoritmo de Cholesky puede fallar cuando la matriz de origen no es positiva semidefinida. Mi implementación detecta ese caso al calcular las raíces cuadradas… y se limita a parar, poniendo un NaN en la celda diagonal donde se ha detectado el problema. Esto significa que el método, en la práctica, asume que la matriz es positiva semidefinida. En mi código, tengo un segundo método, TryCholesky, que devuelve un valor lógico para ver si la conversión fue posible, y retorna la matriz transformada como parámetro de salida.

Desde el punto de vista de un programador de C#, el único detalle interesante es el uso de stackalloc para reservar un array de memoria en la pila, en vez de usar memoria dinámica. Esto es lo que obliga a declarar el método con unsafe.

En rendimiento, el método es más rápido que la «versión base» de la librería que he visto que es más rápida usando sólo C# (usando Intel MKL, no hay competencia posible). Me refiero a la versión base porque, para matrices grandes, las librerías serias suelen dividir la matriz en bloques que se pueden procesar en paralelo. Este código, como ve, no usa threads, instrucciones SIMD y sólo utiliza punteros para la caché. En menos palabras: todo es mejorable.

La distribución normal multivariante es la generalización más inmediata de la distribución normal a un espacio multidimensional. Esto es: cada vez que tiremos los dados, queremos obtener, en vez de un número flotante, un vector de $N$ dimensiones.

La manera más sencilla de definir, y a la vez explicar, esta distribución es constructivamente. Primero tenemos que definir a qué llamaremos un «vector aleatorio normal estándar». Esto es simplemente un vector cuyos elementos son variables aleatorias normales independientes, cada una con media cero y varianza uno… como las que genera nuestro iterador BoxMuller de la entrada anterior.

Ahora supongamos que $Z$ es uno de estos vectores aleatorios normales y estándares, que $A$ es una matriz de dimensiones compatibles con $Z$, y que $\mu$ es un vector que, para simplificar, asumiremos que tiene las mismas dimensiones que $Z$. Entonces, los vectores aleatorios $X$ definidos mediante la siguiente ecuación pertenecen a una distribución normal multivariante:
$$
X = A \times Z + \mu
$$Para nosotros, los programadores, esto simplemente quiere decir que podemos generar vectores aleatorios normales multivariantes generando primero vectores gaussianos independientes y luego transformándolos con una multiplicación matricial seguida de una suma vectorial.

Intuitivamente, es más o menos claro que la suma vectorial nos sirve para mover la esperanza de la distribución, pero no es tan sencillo ver para qué multiplicamos por una matriz. La respuesta es que así conseguimos que las distintas dimensiones de la distribución no sean independientes. La matriz $\Sigma = A \times A^T$ sería entonces la matriz de covarianza entre las dimensiones de la distribución.

Una distribución muy general

La definición constructiva anterior es muy general, con toda intención. De hecho, en la definición más general, los vectores $X$ y $Z$ no tienen necesariamente que tener la misma dimensión, y la matriz $A$ puede ser, en consecuencia, una matriz rectangular.

De hecho, nuestra definición no garantiza que $\Sigma$ sea una matriz de covarianza razonable. Para ello, todos sus elementos tendrían que ser no negativos, y los elementos de la diagonal, en particular, tendrían que ser positivos. Eso no se cumple para cualquier $A$, y cuando no se cumple, no se puede definir una función de densidad para la distribución. Pero cuando la matriz de covarianza está bien definida, ocurre algo interesante, porque la función de densidad asociada se puede escribir de esta manera:
$$
{1 \over \sqrt{(2\pi)^k\vert\Sigma\vert}}e^{-{1\over 2}(x – \mu)^T \Sigma ^{-1}(x – \mu)}
$$Esta definición es casi idéntica a la de una gaussiana escalar. Las diferencias son que utilizamos vectores para el argumento y la media, y que en vez de tener la varianza en el denominador de la exponencial, utilizamos la inversa de la matriz de covarianza (la variable misteriosa k del factor de escala es simplemente el número de dimensiones de la distribución).

Monsieur Cholesky

¿Y si partimos del extremo contrario? En vez de plantearnos la distribución más general posible, teóricamente, podemos partir de una función de densidad ya asumida. Esto es: tenemos una distribución multivariante, y ya conocemos (o podemos calcular) su media y su matriz de covarianza. Tenemos la matriz $\Sigma$, y lo que queremos es encontrar qué matriz $A$ multiplicada por su traspuesta genera la matriz de covarianza…

Permettez-moi de vous présenter M. Cholesky. André-Louis Cholesky fue un militar y matemático francés, muerto en combate pocos meses antes de que terminase la Primera Guerra Mundial. Durante el conflicto, se dedicó a la geodesia y, para facilitar la confección de mapas, inventó eso que ahora llamamos «descomposición matricial de Cholesky», y que podemos entender intuitivamente como una forma de calcular la raíz cuadrada de una matriz.

La descomposición puede aplicarse a matrices hermitianas definidas positivas; si sabemos que la matriz sólo contiene valores reales, esto es equivalente a pedir que la matriz sea simétrica y que la expresión $x^T M x$ sea estrictamente positiva para cualquier vector no nulo. Y, vaya, esto lo cumple cualquier matriz de covarianza decente. Con esta premisa, se cumple entonces que existe una matriz triangular inferior $L$ tal que $M=L \times L^T$. Como ejemplo sencillo:
$$
\pmatrix{1&0.5\cr 0.5&1} = \pmatrix{1&0\cr 0.5&0.866} \times \pmatrix{1&0.5\cr 0&0.866}
$$No voy a describir en esta entrada el algoritmo para calcular la factorización (quizás más adelante), pero es un algoritmo sencillo, que ya implementan la casi totalidad de las librerías numéricas.

Con todos estos elementos en la mano, ya tenemos una receta para generar vectores aleatorios normales con dimensiones correlacionadas:

Necesitamos conocer o calcular tanto la media como la matriz de covarianza de la distribución deseada.
Calculamos la descomposición de Cholesky de la matriz de covarianza.
Podemos entonces usar la fórmula $X=L\times Z + \mu$, donde $Z$ es un vector aleatorio normal estándar que podemos generar con un algoritmo sencillo como el de Box-Muller o el del zigurat.