Cálculo eficaz y rápido de la distancia de Mahalanobis

Question

Supongamos que tengo $n$ puntos de datos $x_1,\dots,x_n$ cada uno de los cuales es $p$ -dimensional. Sea $\Sigma$ sea la covarianza poblacional (no singular) de estas muestras. Con respecto a $\Sigma$ ¿cuál es la forma más eficiente conocida de calcular el vector de distancias de Mahalanobis al cuadrado (de $\vec 0$ ) de los n puntos de datos.

Es decir, queremos calcular el vector $(x_1^T\Sigma^{-1}x_1,\dots,x_n^T\Sigma^{-1}x_n)$ .

Cálculo de la inversa $\Sigma^{-1}$ parece ser bastante lento para matrices grandes. ¿Hay alguna forma más rápida?

Answer 1

1. Sea $x$ ser uno de sus puntos de datos.

2. Calcule el Cholesky descomposición $\Sigma=LL^\top$ .

3. Defina $y=L^{-1}x$ .

4. Compute $y$ por sustitución hacia delante en $Ly=x$ .

5. La distancia de Mahalanobis al origen es la norma euclídea al cuadrado de $y$ :

$$ \begin{align} x^\top\Sigma^{-1}x &= x^\top(LL^\top)^{-1}x \\ &= x^\top(L^\top)^{-1}L^{-1}x \\ &= x^\top(L^{-1})^\top L^{-1}x \\ &= (L^{-1}x)^\top(L^{-1}x) \\ &= \|y\|^2. \end{align} $$