Ich schreibe eine Funktion, um die Mahalanobis-Distanz zwischen zwei Vektoren zu nehmen. Ich verstehe, dass dies mit der Gleichung a * C ^ -1 * b erreicht wird, wobei a und b Vektoren sind und C die Kovarianzmatrix ist. Meine Frage ist, gibt es einen effizienten Weg, um das Inverse der Matrix ohne Gauss-Jordan-Eliminierung zu finden, oder gibt es keinen Weg um diese? Ich suche nach einer Möglichkeit, dies selbst zu tun, nicht mit irgendwelchen vordefinierten Funktionen.
Ich weiß, dass C eine hermitesche, positiv definite Matrix ist, also gibt es irgendeinen Weg, um diese Tatsache algorithmisch auszunutzen? Oder gibt es einen cleveren Weg, den Mahalanobis-Abstand zu berechnen, ohne das Gegenteil der Kovarianz zu berechnen? Jede Hilfe wäre willkommen.
*** Edit: Die obige Mahalanobis-Distanzgleichung ist falsch. Es sollte sein x '* C ^ -1 * x mit x = (b-a), und b und a sind die beiden Vektoren, deren Abstand wir zu finden versuchen (danke LRPurser). Die Lösung in der ausgewählten Antwort ist daher wie folgt:
d = x '* b, wobei b = C ^ -1 * x C * b = x, also löse für b die LU-Faktorisierung oder LDL-Faktorisierung.
Sie können (und sollten!) die LU-Zerlegung verwenden, anstatt die Matrix explizit zu invertieren: C x = b mit a lösen Die Zerlegung hat bessere numerische Eigenschaften als die Berechnung von C^-1 und die Multiplikation des Vektors b .
Da Ihre Matrix symmetrisch ist, entspricht eine LU-Zerlegung effektiv einer LDL * -zerlegung , was du eigentlich in deinem Fall verwenden solltest. Da Ihre Matrix ebenfalls positiv definit ist, sollten Sie in der Lage sein, diese Dekomposition ohne Pivotieren durchzuführen.
Bearbeiten: Beachten Sie, dass Sie für diese Anwendung nicht das vollständige C x = b -Problem lösen müssen.
Stattdessen geben Sie C = L D L* und den Differenzvektor v = a-b an und lösen L* y = v für y (das ist halb so viel Arbeit wie der vollständige LU-Solver).
Dann kann y^t D^-1 y = v^t C^-1 v in linearer Zeit berechnet werden.
Der erste Mahalanobis-Abstand (MD) ist der normierte Abstand in Bezug auf die Unsicherheit bei der Messung von zwei Vektoren. Wenn C=Indentity matrix , reduziert sich MD auf die euklidische Distanz und somit reduziert sich das Produkt auf die Vektornorm. MD ist für alle Nicht-Null-Vektoren immer positiv positiv oder größer als Null. Durch Ihre Formulierung mit der entsprechenden Wahl der Vektoren a und b kann a*C^-1*b kleiner als Null sein. Hoffentlich ist der Unterschied der Vektoren, nach denen Sie suchen, x=(a-b) , was die Berechnung x^t*C^-1*x ergibt, wobei x^t die Transponierte des Vektors x ist. Beachten Sie auch, dass MD=sqrt(x^t*C^-1*x)
Da Ihre Matrix symmetrisch und positiv definit ist, können Sie die Cholesky-Dekomposition (MatLab-chol) verwenden, die die Hälfte der Operationen als LU verwendet und numerisch stabiler ist. chol(C)=L wobei C=L*L^t ist L ist eine untere Dreiecksmatrix und L^t ist die Transponierung von L , die es zu einem oberen Dreieck macht. Dein Algorithmus sollte ungefähr so aussehen
(Matlab)
%Vor%Tags und Links algorithm c linear-algebra matrix