teoria - Distancia Mahalanobis invirtiendo la matriz de covarianza

teoria de covarianza

Question

Estoy escribiendo una función para tomar la distancia de Mahalanobis entre dos vectores. Entiendo que esto se logra usando la ecuación a ''* C ^ -1 * b, donde a y b son vectores y C es la matriz de covarianza. Mi pregunta es, ¿existe una forma eficiente de encontrar la inversa de la matriz sin usar la eliminación de Gauss-Jordan, o no hay forma de evitar esto? Estoy buscando una forma de hacerlo yo mismo, no con ninguna función predefinida.

Sé que C es una matriz definida positiva de Hermitia, entonces ¿hay alguna forma de que pueda aprovechar algorítmicamente este hecho? ¿O hay alguna manera inteligente de calcular la distancia Mahalanobis sin calcular el inverso de la covarianza en absoluto? Cualquier ayuda sería apreciada.

*** Editar: La ecuación de distancia Mahalanobis anterior es incorrecta. Debe ser x ''* C ^ -1 * x donde x = (ba), y by a son los dos vectores cuya distancia estamos tratando de encontrar (gracias LRPurser). La solución planteada en la respuesta seleccionada es, por lo tanto, la siguiente:

d = x ''* b, donde b = C ^ -1 * x C * b = x, entonces resuelve para b usando factorización LU o factorización LDL.

Answer 1

La primera distancia Mahalanobis (MD) es la distancia normada con respecto a la incertidumbre en la medición de dos vectores. Cuando C=Indentity matrix , MD reduce a la distancia euclidiana y, por lo tanto, el producto se reduce a la norma del vector. Además, MD siempre es positivo definido o mayor que cero para todos los vectores distintos de cero. Mediante su formulación con la elección apropiada de los vectores a y b , a*C^-1*b puede ser menor que cero. Esperemos que la diferencia de vectores que está buscando sea x=(ab) que hace que el cálculo x^t*C^-1*x donde x^t es la transposición del vector x . También tenga en cuenta que MD=sqrt(x^t*C^-1*x) Dado que su matriz es simétrica y positiva definida, puede utilizar la descomposición de Cholesky (MatLab-chol) que utiliza la mitad de las operaciones como LU y es numéricamente más estable. chol(C)=L donde C=L*L^t donde L es una matriz triangular inferior y L^t es la transposición de L que la hace triangular superior. Tu algoritmo debería ser algo como esto

(Matlab)

 x=a-b;
L=chol(C);
z=L/x;
MD=z''*z;
MD=sqrt(MD);

Answer 2

Puede (¡y debería!) Usar la descomposición de LU en lugar de invertir explícitamente la matriz: resolver C x = b usando una descomposición tiene mejores propiedades numéricas que calcular C^-1 y multiplicar el vector b .

Dado que su matriz es simétrica, una descomposición de LU es efectivamente equivalente a una descomposición de LDL * , que es lo que realmente debería usar en su caso. Como su matriz también es positiva definida, debería poder realizar esta descomposición sin pivotar.

Editar: tenga en cuenta que, para esta aplicación, no necesita resolver el problema completo C x = b .

En cambio, dado C = LDL* y el vector de diferencia v = ab , resuelva L* y = v para y (que es la mitad del trabajo que el solucionador de LU completo).

Entonces, y^t D^-1 y = v^t C^-1 v se pueden calcular en tiempo lineal.